The easiest way in this case is probably using the command line. Here's what you need to get started:
A copy of the public key (from the key server, for example) saved to a file, let's say key.pub
A copy of the revocation certificate, saved to a file, let's say revoke.txt
Some form of gpg. If you have installed GPGtools, you should be set to go.
First: import the public key into your keyring
$ gpg --import key.pub
The computer says:
gpg: key 07F04249: public key "Not my key <test@example.com>" imported
gpg: Total number processed: 1
gpg: imported: 1
If you want to check your work, you can list the keys that have been imported:
$ gpg --list-keys
The computer says:
/Users/blabbity/.gnupg/pubring.gpg
-------------------------------
pub 1024D/07F04249 2011-11-08
uid Not my key <test@example.com>
sub 2048g/82DDA00F 2011-11-08
Second: import the revocation certificate
$ gpg --import revoke.txt
The computer says:
gpg: key 07F04249: "Not my key <test@example.com>" revocation
certificate imported
gpg: Total number processed: 1
gpg: new key revocations: 1
Check your work again:
gpg --list-keys
The computer replies:
/Users/blabbity/.gnupg/pubring.gpg
-------------------------------
pub 1024D/07F04249 2011-11-08 [revoked: 2011-11-08]
uid Not my key <test@example.com>
Finally: Upload the revoked key
gpg --keyserver pgp.mit.edu --send-keys 07F04249
Of course, replace 07F04249 with the id of your public key (which you can see in the output of the list-keys command).