In order to exchange encrypted e-mails with someone, you have to exchange your Digital Certificates which contain the public keys that you will use for encrypting your communications. In order to ensure the certificate is really for the person you want to talk to, you should either trust the certificate authorithy that signed that certificate (e.g., Verisign) or preferably, verify directly the certificate with your corespondant.

The later can be done by calling the person and once you are sure it his really the person you want to talk to (e.g, by recognizing her voice), ask her to read the certificate thumbprint. On windows computer this can be achieved by viewing the certificate in Internet explorer (tools=>intenet options=>content=>certificates=>otherpeople). The thumbprint is the last field of the certificate and is a string of number of letter like: 2d 37 0a 57 69 e2 75 39 c7 96 90 56 a2 6c 03 18 9b a9 70 1d

See, What is a Certificate Authority? How do I obtain my correspondent digital certificates?