This article is from the PGP FAQ, by Jeff Licquia firstname.lastname@example.org with numerous contributions by others.
It is very easy for someone to generate a key with a false ID and send
e-mail with fraudulent headers, or for a node which routes the e-mail
to you to substitute a different key. Finger servers are harder to
tamper with, but not impossible. The problem is that while public key
exchange does not require a secure channel (eavesdropping is not a
problem) it does require a tamper-proof channel (key-substitution is a
If it is a key from someone you know well and whose voice you
recognize then it is sufficient to give them a phone call and have
them read their key's fingerprint (obtained with PGP -kvc <userid>).
If you don't know the person very well then the only recourse is to
exchange keys face-to-face and ask for some proof of identity. Don't
be tempted to put your public key disk in their machine so they can
add their key - they could maliciously replace your key at the same
time. If the user ID includes an e-mail address, verify that address
by exchanging an agreed encrypted message before signing. Don't sign
any user IDs on that key except those you have verified.