I have been reading up on key signing policies and best practices. Something I have been unable to figure out is how to verify the email address attached to a UID of a GnuPG key.
I can verify the name using an ID, but how do I verify the email address? I am not just trying to determine that the address is valid, but also that is belongs to the person who controls the private key.
The most common case I've seen so far is to sign the key and then send the signed key (well, just the single signature) via e-mail to the purported e-mail address. If there's more than one e-mail address on a key, to each address you only send the signature for this address, encrypted with their public key. Do not upload the signature to a key server or make it available otherwise. Then either the person receives the signature and is able to decrypt it and everything is fine, or they don't and you don't care.
This of course only solves the problem in the keysigning party case (or similar), e.g. you certifying to other people that the ID consisting of name (which you checked with an ID document) and e-mail address (checked with the above protocol) is correct. To be sure yourself you would need to delete the signature locally (or not import it into your keyring in the first case) and then wait until the recipient has uploaded it to a keyserver.
There's a tool that implements this protocol: caff.
Unlike the X.509 certificate model with hierarchical trust starting from root certificates (which are usually chosen by your software vendor/distributor), there is no "default" trust entity to verify user IDs in OpenPGP. Issuing trust is completely left up to you, and a tool named "web of trust" is put in your hands to do so.
It is very important to realize that OpenPGP key servers usually do not do any validations, especially not beyond sending verification mails (so they do not verify the name portion in a user ID).
Some wording needs to be clarified before continuing with the answer: valid keys are those that meet your trust requirements. There are two different kinds of trust, trust in identity (an OpenPGP user certifies another key after claiming to have verified the other's identity, signatures in OpenPGP), and trust in other user's certifications (also called vouching, simply called "trust" in OpenPGP). The terms certification and signature are often used equivalently.
The web of trust is the set of all keys and certifications issued in-between them.
Certifications should only be issued after properly verifying the signee's identity. Usually, this is performed by the signee handing over his key (or fingerprint, to fetch the key from the key servers) and some documents to the signer, for example a passport or identity card. Often, they're performed bidirectional (both parties exchange keys and documents vice-versa), but it could easily be one-directional, too.
OpenPGP is the standard implemented by GnuPG (a free software), but also PGP (where OpenPGP's root came from, but nowadays is commercial software) and a few other products.
If you checked the other party's identity on your own, you can be pretty sure about their identity, thus keys certified by your own key are considered valid. For reaching this, your own key is equipped with "ultimate" trust. All keys equipped with ultimate trust could be compared with root certificate authorities in X.509.
Now it's hard meeting everybody before starting communication, some might live far away and traveling for identity validation might prove hard to do.
This is where the web of trust comes into play. Obviously, you cannot consider keys valid just by looking at their incoming certifications: creating keys and certifications is easy and cheap, you could even fake hundreds or thousands of keys and certifications. To validate another key, you need to construct a trust path between your key (an ultimately trusted key) and the other user, with all keys in-between also being valid.
For example, Alice certified Bob, and Bob certified Carol. Alice can trivially verify Bob's key (she signed it on her own). If Alice also trusts Bob to properly validate other user's identities (ie. Bob is able to realize phishy documents, and has no intent of issuing fake certifications), Alice issues trust to Bob. Now she's also able to verify Carol's key through Bob.
In OpenPGP, there are two levels of trust: moderate and full trust. How to use them is up to you, but GnuPG proposes following trust model: one certification by a fully trusted key is fine (so you really need to know the other's intents well, maybe for friends and family), but three certifications by moderately trusted keys are required (these could -- depending on your personal requirements -- also be people you know less well, for example through open source participations, publications, science, ... Requiring multiple certification paths implements a four-eyes-strategy (well, in this case rather six eyes).
The canonical source of certifications as a foundation of the web of trust are so-called key signing parties, where a bunch of people meets for mutually verifying their identity and signing keys.
There are also some institutions acting as certificate authority in the web of trust, namely CAcert also issuing OpenPGP certifications, and the German Heise Verlag running different German technology magazines.
