What exactly does the "key signing" mean?
So for example I have a private/public GPG key so that people could send me encrypted e-mail, because they know my public key. But: what does key signing mean in this example? E.g.: "a third person signs my public key (how?)."
And the most important: Where can other people see that my key is signed by others?
OK, as you say, you have a private/public pair key so I can send you encrypted e-mail, because I know your public key.
But how do I know your public key? Obviously, because you told me what it was, and if you told me over a secure channel - for example you wrote it on a piece of paper and handed it to me in private - then that's fine.
But if you emailed it to me over an insecure channel how can I know that Eve didn't intercept your email and replace your key with hers? Then Eve could read my encrypted email, because I'd have encrypted it with her key.
This is a real problem because if we've only got the Internet as our communications channel then by definition it's not secure to use for exchanging keys. It can't be, because we haven't exchanged keys yet.
One way round this is to involve a third party who we both trust. Let's call him Bob.
Bob has a lot of secure channels to people. He has one to me and so I know his public key. He has one to you, and Bob knows your public key.
What Bob can do is take your public key, and encrypt the message "Lance's public key is 18348273847473436" with his private key. He then gives that encrypted message to you. Bob has signed your key.
Now, if you want to send me your public key, you just send me the signed key over the insecure channel. I know it came from you, not Eve, because I can decrypt it with Bob's public key, and I trust Bob.
So, we've turned the problem of "Graham and Lance need a secure channel between them" into the problem of "Graham needs a secure channel to Bob" and "Lance needs a secure channel to Bob".
It doesn't sound like we've made things better, until you realise that now instead of worrying about arranging secure channels to D.W. and Lucas and Schroeder and Thomas and Rory and Graham and everyone else on the Internet, you just need to worry about getting a secure channel to Bob, once.
In PGP, key signing refers to the fact that what's often called PGP (public) keys are not just public keys, but certificates.
A public key certificate is the signed combination between a public key, identifiers (and possibly other attributes). Those who sign this document effectively assert the authenticity of the binding between the public key and the identifier, in the same way as a passport issuing authority asserts the binding between the picture and the name in a passport.
X.509 certificates are one type of certificate, the ones most commonly used for SSL/TLS communications. They can only have one signature, which leads to a hierarchical Public Key Infrastructure.
In contrast, PGP certificates can have multiple signatures. A number of individuals could actually vouch for the binding between the public key and the identity referred to in the PGP certificate. These multiple signatures allow to build a Web-of-Trust model, so that you don't have to rely on a single hierarchy to establish trust in a certificate.
When you sign a PGP key (more precisely, the key and its associated identifier), you put your identifier and signature to the list of people who vouch for this. There is a certain responsibility associated with this, because you need to trust that this association is correct via some other means (e.g. by looking at an official form of ID).
For other people to see that your key was signed by others, you can either give it updated versions by yourself (inconvenient) or publish your key to a key distribution server. People willing to use your key would fetch the updated version with new signatures one in a while (or when they need to use and verify it).
SIgning a key is effectively a way of saying that you trust the key is correct and associated with a particular individual or identity (thanks @Bruno). People who trust you may then choose to trust it based on the fact that you have signed it.
Signing means you digitally sign the key certificate. You don't need it, but you will see with PGP for example, that each key on your keyring has a trust value associated with it. Signing the key allows you to move the trust indicator higher.
For PGP, for example, when you have signed the key, you can upload it to one of their pgp key stores so others can see it. Or you exchange keys at a key signing party or in person.
encrypting a public key with a private key is called 'Signing a key'
Key signing in public key systems is a mathematical assertion that there is a relationship between the key (a bunch of numbers in a certain sequence) and the subject (a person or principal identity). Key signing establishes or strengthens trust in that assertion and thereby the validity of a key for some purpose.
In hierarchical systems (eg X.509) a key must be signed by an authority higher in the tree to be considered trusted. In web-of-trust systems (eg classic PGP) users and groups sign keys to show that they trust the identity is associated with the keys. In a hierarchy a specific authority is usually responsible for signing (and issueing) keys. In web-based public key infrastructure (PKI) you can also use independent notaries.
Key signing parties allow for lots of people and a few notaries to gather and quickly collect multiple assertions (signatures) from other people. This strengthens the web and allows users to quickly gain points they may need in systems such as Thawte or CACert to become notaries or unlock perks.
Lets say Alice, Bob and Charlie all use PGP/GPG, so they each generate a keypair now if Alice was to send a message to Bob how does Bob know it was actually signed with Alice's key, it could be a key some attacker just generated and setup in Alice's name. Now lets say Charlie had met both Alice and Bob at separate times, and Charlie signed Alice's key and Alice signed Charlies' key and the same between Bob and Charlie. Now Bob gets Alice's message and says, oh, Charlie has signed this key and I trust Charlie therefore I also believe this message is indeed from Alice.
Now the actual method used to do the signing is the same as the method used to sign any message (the message in this case being the public key and some of it's metadata), and usually one uploads public keys to a keyserver where others attach their signatures.
