The program PGP (Pretty Good Privacy) was initially published by Phil Zimmermann in 1991, in response to U.S. Senate Bill 266 which was designed to force manufacturers of secure communications to provide a "back-door" by which the U.S. government would be able to read those communications. The Bill was ultimately defeated, but PGP was born.
Version 2 became the standard version of PGP in the early 1990's. While Zimmermann was working on Version 3, the U.S. government laid criminal charges against him, accusing him of "exporting munitions". The government wanted to control the public use of encryption, and declared it a type of "munitions" in order to achieve this control. However, the law controlling encryption export in fact made the export of paper copies of the code legal, which was what Zimmermann had been doing. The charges were eventually dropped, and PGP v5 was released. (The hyper-paranoid believe a compromise was reached where Zimmermann introduced a back-door into v5 that the U.S. government could exploit. However, the source code is still open for scrutiny, and this accusation seems unlikely). The ridiculous encryption export law was relaxed in 1999, high grade encryption can now be exported to anywhere except the United State's Standard Arch Enemies (Cuba, Iran, Iraq...).
In the late 90's the company Network Associates, Inc. bought both the rights to PGP and Zimmermann himself (i.e. he is now an employee), and have released PGP v6, which is still free for non-commercial use. A graphical interface was written for the Windows and Mac versions. Out of concern for the commercialisation of the program and the legal encumbrance of the IDEA and RSA algorithms (see below), a group of open-source programmers related to the GNU project wrote GnuPG, a free software (GPL'd) version conforming to the OpenPGP standards.
The two basic encryption techniques are symmetric and anti-symmetric. Symmetric encryption involves only one key, which is used by both the sender for encrypting and the recipient for decrypting. A number of symmetric algorithms exist, including blowfish, Triple-DES, CAST, IDEA. IDEA is, like RSA legally restricted, but the other algorithms may be freely used. An older algorithm, DES, was cracked in 1999 and should now be shunned. A key size of 128 bits is currently considered to be sufficiently secure, key sizes of 56 bits or less can be considered crackable.
The obvious problem with symmetric encryption is the means of distributing the key. Asymmetric (public key) encryption solves this problem by using two keys, one public and the other private. A message is encrypted to a recipient using that person's public key, but it can only be decrypted using the corresponding private key. This means you cannot read a message that you yourself encrypted (unless you also encrypted it simultaneously with your own public key). Hence the public key may be freely distributed to all with no fear of compromising security. The private key, of course, should be carefully protected. Public key algorithms were developed in the 1970's in two main camps. (Beware, I have a habit of mixing the concepts of "public-key encryption" and "asymmetric" encryption up!) The first, RSA (Rivest, Shamir, and Adleman), was patented in the U.S. making its implementation restricted legally (till September 2000). The second, DH (Diffie-Hellman), is not legally encumbered in this way. A key size of 2048 bits is sufficiently secure. Symmetric encryption at 128 bits is roughly equivalent is strength to asymmetric encryption at 2048 bits.
Zimmermann chose to use a kind of hybrid public key encryption for the PGP protocol, incorporating both symmetric and asymmetric encryption methods. The email message is encrypted using a symmetric algorithm with a key size of, say, 128 bits. That key is then encrypted asymmetrically using the recipient's public key with, say 2048 bits, and the entire message (symmetrically encrypted body and asymmetrically encrypted key) is sent together to the recipient. The message may additionally be digitally signed.