To send an encrypted message, you need to use the recipient's public key in combination with your private key. Evolution handles the encryption, but you need to get the public key and add it to your keyring.

To get public keys from a public key server, enter the command gpg --recv-keys --keyserver wwwkeys.pgp.net keyid, substituting keyid by your recipient's ID. You need to enter your password, and the ID is automatically added to your keyring.

If someone sends you a public key directly, save it as a plain text file and enter the command gpg --import to add it to your keyring.