Signing a public key

This answer describes digital signatures which are not necessarily what is needed. While digital signatures can be used with GPG, they are not required.

When using a digital signature, to sign a public key you need a public/private key pair of your own. The way in which you generate the public/private key pair and sign the document/key depend on the protocol you are using.

When you sign a document/key you will use your private key to encrypt the document (called signing) and then distribute your public key to others so that they can decrypt your document and verify that they receive the original text back.

The idea is that the private and public keys come as a pair and it is extremely difficult to generate an encrypted copy of the original document that will properly decrypt with your public key without access to your private key (which you keep secret).

Your public keys should be "well known" in the sense that it should not be only distributed with the signed document or the public/private key used to sign could have been entirely forged.

Note that since this your public key is known "publicly" anyone can decrypt this document. Digital signatures are simply used to verify the authenticity of the document, not keep it secret. For a broader description of public-key cryptography and its many uses please check the public-key cryptography page on Wikipedia.

This link on PGP may be of use, and here is some information on key exchange protocols.