GPG stands for GNU Privacy Guard. It implements the OpenPGP standard for asymmetric cryptography to provide privacy (when encrypting) and authentication (when signing). Encrypted data can only be decrypted by the intended recepient, and signed data cannot be altered without invalidating the signature.
While GPG can be used for any data, I use it primarially for email. Anyone who has my public key can send email which only I can decrypt, and can confirm that messages from my email address were signed using my secret key. Likewise, for anyone who shares their public key with me, I can send private messages to you, and I can confirm that messages from you are not foarged.
OpenPGP is not natively supported by the email clients I use, but is available through a plugin. I use Enigmail for Thunderbird, and GPGMail for Mail.app. (If you're using Linux, I'm going to assume you're clever enough to figure it out yourself.)
I don't understand it fully, so don't take my description as authoritative. This is meant to convey the basic principals involved, simply enough than any english speaker should be able to understand, but should be read with the understanding that it is no more than a rough outline of how things actually work.
There are some mathematical operations that can be done fairly quickly, but take a very long time to reverse. For example, finding the square of a number is significantly faster than finding the square root of a number. There are operations with a larger disparity than that, and asymmetric cryptography takes advantage of that disparity.
if you start with some very big numbers – 256 bits is up to 78 decimal digits – and do the cheap side of one of those disparate operations, reversing that operation will take a very long time. The more bits you use, the longer it takes in both directions, but while the cheap operation might take several minutes, the expensive reversal might take several hundred years. In principal, assymetric cryptography is trivial to break, but in practice you won't live long enough to do it.
Generating keys essentially consists of picking some very large numbers for the secret key, and performing the cheap side of some operations to generate the public key. Data encrypted using the public key cannot be decrypted without the big numbers in the secret key, which means you must either have the secret key, or an awful lot of patience. Data signed using the secret key can be confirmed using the public key and some inexpensive operations, but generating the signiture from the public key would require the same prohibitively expensive operations.
Of course, if there were to be a sudden and dramatic increase in computing power, keys that are too short would suddenly become useless – the expense in regenerating the secret key from the public key would no longer be prohibitive. While I doubt that can be proven impossible, I also doubt it will happen. We have some idea how fast computing power is increasing, so for any particular key length we can make some estimate of when private data will need to be moved to a longer key. The most dramatic change I think might actually happen would be a relatively fast increase in computing power, which would require private data to be transfered from a shorter secret key to a longer secret key much sooner than expected.