Every e-mail that you send across the Internet is sent in plain text, meaning any individual sitting at one of the many hops between you and your recipient can read the message. And sniffing e-mail is not hard to do even for amateurs. Many ISP's have data retention policies where they retain every e-mail and website visited by every subscriber for a period of months (and sometimes years). Furthermore, the FBI is lobbying Congress to pass a law making such practices mandatory and expanding the length of time ISP's must retain data to 2 years. The NSA, as we all know, was caught spying wholesale on Internet communications at the various backbones (AT&T being one culprit that helped with the spying). If you live in the UK or many other countries, you already have Orwellian laws on the books making data retention mandatory. So, one must ask oneself: "Do I really want my ISP having access to all of the personal e-mails I have sent for the past couple of years?" I don't know about you, but I don't.
Don't get confused
Therefore, I will use this post to cover e-mail encryption using the best tool for the job: GnuPG.
Many people confuse the SSL/TLS connection that most mail providers (like Gmail) use on their servers for end-to-end encryption. Please do not fall into that camp. The truth is, SSL/TLS only serves to encrypt your connection between yourself and your mail server (i.e. it encrypts your login session); it does nothing to secure any e-mail you send back and forth to your contacts! Those messages are still being sent from your mail server to your contact in plain text.
Some terminology defined
There are a few terms that need to be defined so that the user understands how PGP/GPG works. In the field of cryptology there are two main categories of encryption ciphers: symmetric and asymmetric. Without getting into a lot of needless history, symmetric ciphers are much older and are generally much faster. Asymmetric ciphers (also known as "public key cryptography") have only been around since the 1970's. The two categories of ciphers are based on different "problems" that make cryptanalysis difficult. As a result of their differences, asymmetric ciphers are a lot slower and are generally only used when key exchange is difficult to do securely.
An asymmetric cipher (or public key cipher) has the interesting property of utilizing two keys that are mathematically related to each other. One key is the public key, which can be safely distributed over an insecure medium like the Internet without fear of it being intercepted. (If it's intercepted, it will do the attacker no good -- he still cannot decrypt messages without your private key). By having your public key, a contact can send you encrypted messages that only you can decrypt. So, one can think of public key crypto in the following way: the public key is used to encrypt messages to the key owner and the private key is used by the key owner to decrypt those messages. As long as the private key is kept away from everyone but the owner, the public key does an attacker no good whatsoever. Just remember: the public key is used to encrypt and the private key is used to decrypt. Public key crypto was one of the biggest breakthroughs in the history of cryptography and effectively solved the problem of distributing keys securely. This is why it is essential to use it for e-mail encryption.
GnuPG (and PGP) is what is known as a hybrid cryptosystem; that is, it utilizes both asymmetric and symmetric ciphers. The hybrid system solves the problem of the slowness of public key crypto (like RSA). What GnuPG does is use the asymmetric cipher to encrypt the key to a symmetric cipher. That way, the slow as molasses asymmetric cipher is being used only to encrypt a very small amount of information. The bulk of the message is being encrypted by a fast symmetric cipher.
What you need
This tutorial is focused on Linux (or other *nix) users. If you're on Windows, you can use the free version of PGP which should be fully compatible with GnuPG. Alternatively, you can use GPG4Win. If you're a Linux user, you should already have GnuPG installed on your machine out of the box. To check, run the following command:
Generating a key
The first thing to do is create a key pair. It's recommended (for reasons I wont go into here) to generate an RSA key pair. The minimum recommended length is 2048 bits, but with the power of most modern computers, you should be fine with a larger key. The maximum key length is 4096 bits and there's no reason to make it larger than that (even though you can in theory). I generated a key of 3248 bits for my personal use, which should be enough to future-proof it for at least 20 years as well as allowing me to avoid overwhelming any mobile devices my key might be used on. 
When generating a key, we first want to pass some basic preferences to it so that the key will use these preferences out of the box. So, to generate a key, fire up your terminal and cut and paste the following:
gpg --cert-digest-algo=SHA256 --default-preference-list="S9 S8 S7 S10 S13 S12 S11 S3 S2 S4 H10 H9 H8 H11 H3 Z2 Z3 Z1 Z0" --gen-key
This will set your preferences so that your recipients will encrypt messages to you using the following cipher order of preference: AES256, AES192, AES128, TWOFISH, CAMELLIA256, CAMELLIA192, CAMELLIA128, CAST5, 3DES, BLOWFISH
It will set your hash preference as follows: SHA512, SHA384, SHA256, SHA224, RIPEMD160, SHA1
If you don't like this order, you can change it accordingly, but I think what I have listed is the strongest option. Whatever you do, you will probably want to use AES and SHA256+ as your cipher and hash combination due to their widespread use in various OpenPGP compliant programs. If you use CAMELLIA, you might notice that older versions of GnuPG and PGP won't recognize it, since CAMELLIA was only recently added to the OpenPGP specification.
When asked what type of key to create, be sure to pick option 1 (RSA/RSA).
When asked for key-size you can either keep it at 2048 or increase it to something like 3072 or 3248 (I do not recommend going up to 4096 due to speed issues).
It will now ask you to enter an expiration date. If you are using a 2048 bit key, it might be wise to set a limit (say 10 years from now). If you pick a 3072+ bit key you can probably safely make it expire after 20 years or more. Or, probably a better option, is to make it so that it never expires. If factoring techniques or computer technology becomes good enough to crack a 2048+ bit key you can merely revoke the key and create a new one (more on that later). So, it is probably best to set no expiration date here.
Next it will ask you to enter your name (first and last), your e-mail address you want associated with the key, and any other comments you might wish to add. Typically your name and e-mail address are good enough here.
Finally, it will ask you to enter a passphrase. You should pick a passphrase that is as strong as the ciphers you will be using.  I recommend at least a 20 character random password. Since most people can't remember 20 random characters, a better way is to take a line from your favorite book or poem and use the first letter from each sentence. For instance: "Mary had a little lamb a lamb that was as white as snow" would be "mhallaltwawas."  To further complicate it, you could randomly make some of the characters capitalized or substitute them with other characters. So you might end up with: "Mh@11A!tWaWAs." The latter is much stronger than the former. You can also download and use my password generator that I wrote for Linux by either adding my PPA (ppa:rookcifer/pypass) if on Ubuntu or by downloading it from my sourceforge page.
After all of this is done, you will see a screen prompting you to move your mouse or type on the keyboard in order to gather entropy for key creation. Random data gathering is highly crucial to creating encryption keys, so I recommend you move the mouse around and/or open an empty document and blindly begin typing nonsense in it. 
After this is done (it could take a few minutes) you will see a screen like this:
Before we continue we should take the time now to generate a revocation certificate. A revocation certificate is used to revoke your key should your private key get stolen or if your key has become too weak in the face of computational advances or academic attacks on RSA. To generate the certificate, do the following:
gpg --output revocation_cert.asc --gen-revoke KEY-ID
Where "key-ID" is the 8 digit key ID. Your key ID can be found by running:
The key ID will be the top 8 digit hexadecimal string beside your name and email. The revocation certificate will be found in the current directory you are in. I recommend moving it to your ~/.gnupg folder. Just be sure to keep it safe and remember where you put it!
What good is a public key unless other people can get it in order to send you secure messages? Well, instead of having to manually send it to all of your contacts, you can merely upload it to a key server. There are probably a couple dozen key servers around the world and they all sync with each other. So, when you send your key to one server, it will automatically get sent to them all eventually. To do this, type the following command:
gpg --send-keys --keyserver pgp.mit.edu KEY-ID
Again, the key-ID is the 8 digit ID that you find when you run gpg --list-keys.
Now you should seriously consider backing up your entire key-ring to a safe location. This might be a thumb drive or CD that you plan on storing in a safe, or you could do what I do and simply put them in cloud storage. Don't worry, backing them up to the cloud is perfectly safe if you encrypt the key-ring first. Even though the private key is already encrypted on your drive, I like to encrypt it a second time before I send it to the cloud. Here is the easiest way to backup your key-ring.
1) Compress your entire ~/.gnupg directory. If you're on Ubuntu you can merely right click it and hit "compress." Compress it to a tar.gz archive and save it to, say, your desktop. (NOTE: When you save it to your desktop, be sure to change the name to something other than .gnupg because any file that begins with a "." will be hidden from view).
2) There are two ways you can encrypt this archive. First is by using your GPG public key and the second is by merely using a symmetric cipher with a pass phrase. I prefer the second option.
3) GPG can be used to encrypt individual files with a symmetric cipher. To encrypt the archive you just made, type the following command:
gpg -ca --cipher-algo AES256 --s2k-digest-algo SHA512 NAME_of_FILE.tar.gz
It will ask you for a pass phrase. In this case, I recommend generating one of 40 random characters (which will match AES256 in strength). You can save the pass phrase and keep it in a text file locally on your hard drive. Better yet, you should store the pass phrase on a CD or USB key. This is safe to do since this pass phrase is being used to secure the file when it's in the cloud. Someone who has access to this file in the cloud probably isn't going to have access to the pass phrase you have stored locally. Now if you ever lose your hard drive due to a crash, etc., then you can recover your GPG keys by downloading the archive from the cloud and unlocking it with this pass phrase you have stored.
A word on key signing
GnuPG is used for much more than merely encryption. Probably a more widely used feature is for authentication; that is, digitally signing an e-mail or a document and allowing someone else to verify that you really did sign it. Of course, the only way they can verify that you signed it is if you and the contact have verified each other's keys. So, this is where key-signing comes into play.
Key-signing is where you set the trust you have that someone else's public key that you imported to your key-ring really does belong to them. There is a lot that can be said about key-signing (since it is so much a part of the Web of Trust model) but the bottom line is this: do not sign someone else's key unless you are 100% sure that the key you have really belongs to them. The best way to verify it is in person with photo ID's. You view their photo ID and their GPG key fingerprint. You then sign their key and send the key back to them.
There is something called a key-singing party that some code developers and other such technically inclined people will use in order to verify a bunch of keys at once and to create their own Web of Trust. You can see how to conduct a proper key-signing party here.
That's it. Your key is created and backed up securely. The final step is to set it up for use in your favorite e-mail client. If you use Gnome, I recommend Thunderbird and if on KDE, I recommend Kmail. If you're on Ubuntu, the Ubuntu wiki has a very nice step-by-step tutorial in getting your key working in your e-mail client of choice. You can view that here.
1) The RIPA Act also mandates that if the police come a-knocking, you must give up your encryption keys or else face jail time. This has already happened in a few cases.
2) The NIST says a 3072 bit RSA key is equivalent in strength to an AES-128 key, while ECRYPT claims it takes a 3248 bit RSA key to equal a 128 bit symmetric key.
3) A 128 bit cipher should be protected by at least a 128 bit pass phrase. In order to achieve such a pass phrase, one must use a completely random string of 20 characters (using all 95 printable ASCII characters).
4) Actually, "Marry Had a Little Lamb" is probably not the best phrase to use. In reality, you will want to use something much more obscure, yet easy to remember. An even better option would be to make up your own phrase.
5) I have noticed that if you move your mouse very slowly in random motions (like 1/2 inch per second), then /dev/random spits out more data more quickly than if you move the mouse very quickly. Why this is, I don't know.
6) Actually, the private key is already encrypted with your pass phrase. Therefore, an attacker would have to have physical access to the private key and then crack your pass phrase.