This is a great how-to covering gpg and keys. well worth the time to read and review to get an understanding of keys, keyrings, keysigning, etc..
it will explain how to retrieve that users public key,
how to sign that users key,
how to upload that signed key back to the key server
how to view the keys in your ring.
I know the enigmail plugin for Thunderbird allows you to do all those functions through a GUI, I'm not sure what options evolution gives you, since I never run evolution. .
From the looks of the gpg GUI in evolution you should be able to import public keys from a keyserver easily enough.. http://support.real-time.com/linux/e...lutionpgp.html