Phil Zimmermann released the original pretty good privacy (PGP) program in 1991. Almost immediately, the US government filed a lawsuit to block the program's distribution but later withdrew the lawsuit. Because of the quality of its encryption, the US government considered the program munitions and thus permitted export of the program outside the United States with a permit only. By 1996, the Massachusetts Institute of Technology (MIT) was distributing a free version of the software within the United States, and a commercial version was available at http://www.pgp.com (http://www.pgpi.com for foreign parties). Because PGP uses RSA as a public-key algorithm and the patented International Data Encryption Algorithm (IDEA) as a symmetric algorithm, the software can't be distributed completely for free. (MIT's patent for RSA expired in September 2000, but the IDEA patent doesn't expire until 2011.)
The Gnu's Not UNIX (GNU) Privacy Guard (GnuPG) project uses only nonpatented, encumbered algorithms to emulate PGP functionality. The default algorithms are the digital signature algorithm (DSA, sometimes referred to as Digital Signature Standard—DSS) and the El Gamal algorithm (ELG), but GnuPG also supports other algorithms, including RSA. GnuPG uses two types of cryptographic algorithms: symmetric and asymmetric (also known as public-key cryptography). The former uses one key to scramble data and unscramble data. For years, Data Encryption Standard (DES) was the primary standard for symmetric cryptography, but in 2001, Advanced Encryption Standard (AES) superseded DES as the federal standard. For some time, many experts have considered standard DES to be cryptographically unsafe, so GnuPG can use AES and Triple DES (3DES), which is stronger than standard DES. The central problem with symmetric cryptography revolves around key distribution. Having only one key for both decryption and encryption means that the key must be passed back and forth between users, creating a security risk. Public-key cryptography solves this problem in an ingenious way. RSA and its descendents, such as DSA, use the concept of trap-door functions and primes. A trap-door function is one that's easy to compute one way but nearly impossible to reverse. For RSA, this computation is the product of two large prime numbers. Knowing one makes solving the other easy, but knowing neither makes solving either extremely difficult. (This explanation is a gross oversimplification but gives you a basic idea of how the math works.)
This system introduces the idea of key pairs. Each key pair contains a public key and an associated private key, which are initialized at the same time. The public key can be shared with the public at large. The private key is used to decrypt data that was encrypted with the public key, thus paving the way for secure email. For example, if I publish my public key, you can download the key, use it to encrypt an email message, then send me the encrypted message, which I can decrypt by using my private key. You can also use key pairs to create digital signatures. When you use your private key to sign an email message (or other data), anyone who has your public key can verify that the data truly originated from you. For more information about cryptography, I suggest reading Bruce Schneier's canonical Applied Cryptography (John Wiley & Sons, 1996).