Verification is part of any security system. SSH, FTP, POP, and IMAP servers ask for your password before it lets you log into the machine, get your files, or snag your email. NTP can be configured to require keys before it’ll let you mess with it’s clock. CIFS requires a password or kerberos tickets before granting you access to shares.
Now some of the above examples can be done without a password, true enough. FTP can use the anonymous account. NTP keys are seldom used between end hosts and stratum 2 servers. CIFS guest shares are (overly) common.
PGP falls into the same boat. In order to use PGP safely, you need to verify that the public key you have truly belongs to the individual or organisation you expect. Remember – anyone can create a PGP key with any name/comment/email data that they want. I could create a key with “George W. Bush (Texan) firstname.lastname@example.org” just as easily as he could. 
To verify the key, you need to communicate with the actual party in a way that you know it’s them. For example:
Get together with the person directly, and verify their identity. For example check out their driver’s license or some other presumably official form of identification. Make flattering comments about how they’ve lost weight to make things less formal and invasive. Suggest their hair colour is a few shades to the grey side from what they have listed.
On the phone
If you know the person well enough to recognise their voice, no reason you can’t verify keys over a phone call. Ask a few questions that only they could answer, such as “What’s your favourite burger topping” or “Where were we when you first taught me to compile my own kernel?”
The important thing is that you have verified that they are in fact the person they claim to be, and that they are the person you are communicating with when you verify the key.
So, having established communication with the person, you need to exchange the information about your key. There are three crucial parts of the key, and you can find them in gpg –fingerprint keyid output:
$ gpg --fingerprint email@example.com
pub 1024D/D5D3BDA6 2003-12-14 John Doe (My First PGP Key) <firstname.lastname@example.org>
Key fingerprint = 0E43 DC31 C484 431C 5B07 3875 7B2D D3D8 D5D3 BDA6
The important parts are:
Key bits, KeyID, and Key Type.
Above, the Key Bits (i.e. the key strength) is 1024, the Key Type is DSA (noted by the ‘D’ after ‘1024’), and the KeyID is D5D3BDA6.
The KeyID is just a handy way of accessing the key – you use it when you upload or download keys from keyservers, for example. The Key Bits determines the strength of the key. The algorithm, DSA vs RSA for example, determines how the key is used internally. Not all versions of PGP software support both keys (RSA was patented until 2000, for example.)
One interesting tidbit: For DSA keys, you can actually skip verifying this part – notice that the last eight characters of the fingerprint (D5D3 BDA6)) are simply the KeyID. Verifying KeyID isn’t required in that case, but it can’t hurt.
The fingerprint above is 0E43 DC31 C484 431C 5B07 3875 7B2D D3D8 D5D3 BDA6
The fingerprint is essentially a hash of the public key information. Rather than verifying all thousand-odd bits, instead you verify the hash, which is a 20 byte string.
It is not likely that you’ll be sitting down at your computer when the party to be verified has their key on them.  Instead, you’re more likely to meet at lunch, or a PGP keysigning party. In these cases, the easiest way to exchange keys is to have printed out your fingerprint information ahead of time on a piece of paper, verify they are whom they claim to be, and exchange paper fingerprints. You should do something, such as sign the paper itself, to be sure you remember that you’ve verified this key.
Once you have the person’s fingerprint, having already been verified with the human himself, you can sign the key at home at your leisure.
So, how do you sign the key? That’s next week’s topic…
 Ok, perhaps I’d be able to do so sooner than the current US Commander in Chief. They’ve never been known for their technological savvy. In fact, I think I could handhold my 4 year old daughter through it faster.
 You wouldn’t want to verify and sign the key with them there anyway, to avoid them shoulder surfing your password.