Am not sure where this is the right place to ask this
Someone has asked me to sign their public key, how do i do that?
His public key has Version: GnuPG v1.2.1 (GNU/Linux)
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.
To sign someone's public key, you would have to have your own public/private key pair. We'd need more detail, but it sounds like somebody is trying to build up a "web of trust" around their public key. I am sure the kind of person who asked you to do that would enjoy explaining in more detail how to do what they're asking, or you might try searching for "Web of Trust". If that's not what you're looking for then please expand and we'll try to help.
There are some good answers in this thread on the theory, but not much on the practice.
The best way to learn PGP (GnuPG is an alternate implementation) is to use it. I'd recommend, even if you don't use Thunderbird as your primary email client, install Thunderbird and install Enigmail with GnuPG. http://enigmail.mozdev.org/documentation/quickstart.php
PGP is a really good idea, but it's hard to wrap your head around. The longer you spend using it, the more sense it will make.
For mac users you can download a software known as wija link text, this will help you with many issues with regards to public and private keys also signing