I use GnuPG to sign and encrypt e-mail. My public key is here.
While it's not possible to encrypt messages to people who aren't known to use GPG or some other OpenPGP-compliant program, it's still possible to sign them. The signature will simply be an unusable attachment to the mail if they don't use GPG.
One theory is that you should sign all mail that you send, no matter what, since then any unsigned message purportedly sent by you will immediately arouse suspicions.
On the other hand, you should never expose your private key or its password to untrusted systems, which is precisely what I would need to do e.g. when writing e-mails from work. So unless I'm at home on one of my trusted computers, I can't sign messages.
The upside is that when you get a message from me that is signed, you can be that much more certain that it really was me who signed it. And when you send me an encrypted message, you can be sure that I only read it on a trusted computer.
If you would like me to sign your public key, you can write an e-mail and ask for a meeting. I live in Stockholm, Sweden. See also Debian's keysigning page.