You need to do some sort of key exchange with the recipient, in which case you both need to have your keys signed and stored with a Public Key Infrastructure. This is how PGP works - people register their keys with keychains that can be publicly searched and members of that keychain sign these keys for them, cryptographically, to indicate that they may be trusted.
If you check something like UKNOF you'll note there are key signing sessions scheduled - this is why: in-person verification of keys.
Your private key is signed by a certification authority and is kept secret, your public key is signed by other people's private keys to build up a web of trust.
Not sure how familiar you are with asymmetrical cryptography but it's an entire thing on its own.
If the people you are trying to reach have public keys signed and on public key chains you're good to go otherwise the best you can do is rely on transport level encryption which you can ensure on your side though not, as far as I know, on the other.
I hope this helps. Unfortunately I've work to do so can't go into asymmetrical / public key cryptography, key chains, PKIs, CAs, etc, etc, in more depth.
EDIT: NB in real-time communications, messaging applications, etc, where you can set up a direct session to the other device you can perform zero-knowledge key exchange. My friend the good Dr Mike Pound explains:
[youtube]https://www.youtube.com/watch?v=jkV1KEJGKRA[/youtube]
More on Diffie-Hellman:
[youtube]https://www.youtube.com/watch?v=NmM9HA2MQGI[/youtube]
And deeper into the maths:
[youtube]https://www.youtube.com/watch?v=Yjrfm_oRO0w[/youtube]