These step-by-step instructions are based on GnuPG for Linux -- if you use a version of GnuPG for a different OS then you'll need to follow the same instructions in general, but the commands to use and output generated may possibly be different in certain cases.
This guide was heavily based on a document written by V. Alex Brennen, to whom I am indebted.
1) Get a copy of the key from a keyserver. You'll need to use the Key ID listed in the papers you kept from the party (you did keep them, didn't you?). For the purposes of this guide, we'll assume you're working from my key, which has the ID 5BE02EA6:
[fpb@delirium](~) gpg --keyserver pgp.mit.edu --recv-keys 5BE02EA6
If you get a read error, it means the server is overloaded. Try again in a few seconds, or use a different server (see http://www.pgp.net/).
2) Fingerprint and verify the key:
[fpb@delirium](~) gpg --fingerprint 5BE02EA6
GnuPG will output the fingerprint of the key, and you can check it against the checklist you were given at the event.
3) Sign the key:
[fpb@delirium](~) gpg --sign-key 5BE02EA6
How carefully have you verified the key you are about to sign actually belongs
to the person named above? If you don't know what to answer, enter "0".
(0) I will not answer. (default)
(1) I have not checked.
(2) I have done casual checking.
(3) I have done very careful checking.
Your selection? (enter '?' for more information):
The checking-level you assing is up to you, of course -- for most participants in Compsoc keysignings you will be able to choose the highest level ("3") as the keyowner will have provided very clear proof of his/her identity.
(I would advise using level 2 to sign the keys of people unknown to you who have certified their identity to your satisfaction using photo ID, and level 3 for people who you know personally. But using level 3 for users with UIDs in durham.ac.uk, even if you don't know them personally, is acceptable to my mind because their campus card provides a provable link between them and their durham.ac.uk email address.)
Are you really sure that you want to sign this key
with your key: "Fred Bloggs <f.p.bloggs@durham.ac.uk>"
I have checked this key very carefully.
Really sign? yes <return>
For keys with more than one UID associated (i.e if you see the message 'Really sign all user IDs?', see What do I do about multiple UIDs below.
If you have multiple private keys, you can specify which of your private keys to sign the other person's public key with like this:
[fpb@delirium](~) gpg --default-key <Key-to-use> --sign-key 5BE02EA6
4) Upload the signed key to the keyserver:
[fpb@delirium](~) gpg --keyserver pgp.mit.edu --send-key 5BE02EA6
gpg: success sending to `pgp.mit.edu' (status=200)
5) Repeat for each key you need to sign.
Other useful commands
gpg --refresh-keys (with --keyserver as appropriate) will update your keyring with all the keys you know about, whether you've verified them or not. This is useful to slurp all the other participants' signatures into your keyring.
gpg --update-trustdb will offer you each key you've validated in turn, and ask you how much you trust them to validate other keys. By default gpg doesn't alter your trust in a key when you sign it (you'll see it listed as -/f meaning full validity (because you've signed it yourself) but unknown trust. Going through each key with --edit-key is very time consuming, so you can use this command to do things quickly.
(Thanks to Farnz for drawing my attention to the existence of these commands.)
What do I do about multiple UIDs?
Keys often have multiple UIDs associated with them, for which you may not have seen proof of ownership at the keysigning. Typically at a Compsoc keysigning a keyowner will be able to provide easy proof of their ownership of a @durham.ac.uk email address (their Campus card) but may not be able to certify beyond reasonable doubt their ownership of other addresses used in their key.
It is very simple to check the validity of these other UIDs: simply send email encrypted with the keyowner's secret key to each uncertified email address. If the recipient can decrypt the message then he/she is the owner of the secret key, which you have verified belongs to the owner of the certified UID, and you can be sure the extra UIDs correspond to the same person or entity.
If you are only prepared to sign UIDs for which you have seen absolute proof of ownership, you can use gpg --edit-key (or type 'no' at the 'Really sign all User IDs?' prompt) to choose which UIDs on a key to sign: see the GNU Privacy Handbook.