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.
Got a comment? Spotted an error? Found the instructions unclear? Send feedback about this page.