No Linux e Windows, você pode usar o Mozilla Thunderbird com o Enigmail add-on que permite assinar e criptografar mensagens (e funcionará melhor se você não usar mensagens formatadas em HTML).
Para Android, o K-9 funciona muito bem. Embora eu não tenha usado nenhum recurso de GPG com ele, parece que APG oferece uma boa integração com o K-9.