I'm assuming you've installed Gnu Privacy Guard (GnuPG, or GPG). It
should be available as a package for your distro, and I believe some
other programs are front-ends for gpg. I'm also assuming you've created
your own key (otherwise you're probably not interested in this at all).

First, you need the key you want to sign. Your mail program may fetch
them automatically, or not. You can perform this step anyway, and it
won't hurt anything. Find the Key ID in the PGP goop in the message. In
this message you should be able to see key 10775916, which is my key ID.
To fetch it...

$ gpg --keyserver hkp://pgp.mit.edu --fetch-keys 10775916

Then it's easy to sign it...

$ gpg --sign-key 10775916

You'll be shown what you're about to sign and prompted. If you have more
than one signing key of your own you may be prompted to select which one
to use as well. Answer 'Y' if it's what you meant to do. Now we upload
it to the keyserver...

$ gpg --keyserver hkp://pgp.mit.edu --send-keys 10775916

If you configure your ~/.gnugp/gpg.conf to include "keyserver
hkp://pgp.mit.edu" or another keyserver, you can leave it out of the
command line stuff. I chose that server because it's usually up, seems
to propogate out to other servers well, and has an ok web interface.

Last, but not least... don't go signing keys if you don't know who they
are, really. I have signed Alan Dayley's, and Joseph Sinclair's, but I
know them personally and have comfirmation that the email addresses and
keys really belong to them.

Ding. That's it!

-- 
Darrin Chandler            |  Phoenix BSD User Group  |  MetaBUG
dwchandler@stilyagin.com   |  http://phxbug.org/      |  http://metabug.org/
http://www.stilyagin.com/  |  Daemons in the Desert   |  Global BUG Federation