OpenPGP does not know a central certificate authority like X.509 / S/MIME does, so you need to find a trust path from you to the (probable) key owner in the web of trust yourself.
The easiest way is to directly test ownership of the other's key, but that requires meeting the other (for verifying his ID) and/or knowing the other very well (then you could be fine by phoning him, asking him for his fingerprint, and maybe some question only he could answer). In the end, it's at you to decide how to verify the other's identity and key ownership.
If you can't do that, do following:
- Get into the web of trust. Get your own key signed, go signing other keys. Visit key signing parties, of try to find (well-connected) OpenPGP users eg. on . Nice spots to get your key signed are also meetups of your local Linux/Unix user group and (at least in Europe) pirate party meetings. I'd also recommend to sign up with CAcert, which originally hand out X.509 keys, but along the way are the biggest "certificate authority" withing the OpenPGP web of trust. Lots of CAcert users also have an OpenPGP key and will be glad to sign yours when meeting for CAcert assurance!
- Validate the other's key. If you were able to directly validate the other's key (by meeting him somehow, and checking his ID if you do not know him very well or whatever is your policy), you will have to find a trust path. This means, by issuing trust, you trust in signatures issued by another one. You could trust a good friend or colleague of whom you're sure he's doing well in signing keys. If you agree with the way CAcert does, this is a great way to issue trust for a rather large part of the web of trust (and in my opinion, they're doing really well).
For more details on trust, read the GnuPG's manual page on trust, and also this answer of mine on another question.
