Για Ubuntu χρησιμοποίησα αυτόν τον οδηγό:

http://ubuntu-tutorials.com/2007/08/14/privacy-and-encryption-with-pgp-signing-and-encrypting-email-files/

και η κρυπτογράφηση δουλεύει άψογα στον Thunderbird. Δεν έχω δει πως γίνεται αν ο Thunderbird είναι σε Windows - μάλλον όμως χρησιμοποιώντας το enigmail και το gpg4win. (το gpg4win έχει και plugin για το outlook)
Για να επικοινωνήσεις με κάποιον πρέπει να του στείλεις το public key. Υπάρχουν public servers που μπορείς να κάνεις upload το κλειδί σου και να το βρίσκει κάποιος από εκεί. (τους βρίσκεις από τα προγράμματα που διαχειρίζονται τα κλειδιά)