If you're using Thunderbird or mutt, it's really easy and there are several tutorials out there that will be helpful.

If you're using webmail (particularly Gmail), it's easy to do badly, and I'm not aware of a way to do it properly (short of manually encrypting everthing and copy/pasting it).

Setting up the keys, though, is really easy on Linux: http://www.enigmail.net/documentation/gpgsetup.php#generate