The "Web of Trust" is a picture of the relationships between signed keys and the assignment of trust.
PGP does not consider a key to be "Valid" unless it has been signed with by your key or by keys that you have signed and set as a trusted or meta-introducer. A signature can still be verified with an invalid, unsigned key, the difference is that when you sign a key you have (hopefully) satisfied yourself that the person who owns it is actually who they claim to be and it is their key that you are signing.
A good signature from an invalid key means that the message or file that was signed has not been altered. The key being invalid means that you have not signed it nor has it been signed by anyone whose key you have set as a trusted or meta-introducer.
To sign someone's pgp key:
Open PGPKeys and select the key that you wish to sign. Right click on it and select Sign.
The 'PGP Sign Key' window will open. This window will show the key that you have selected and it's Hexadecimal fingerprint. If you are satisfied that they key is valid (Either you recieved it directly from the owner or have otherwise verified who owns the key.) then you can sign it with your key and make it valid. [One way to verify the ownership of a key is to verify the hexadecimal fingerprint with the owner.]
Once you have signed the key it will have a green icon in the Validity column of PGPKeys. You can keep the signed copy of the key on your local keyring, or you can export it with the signature to a certificate server. By exporting the signature, you are making public your claim that the key is valid. Anyone who completely trusts your signature will completely trust the signed key.
You can also grant the key the ability to validate other keys, by setting the key as a trusted or meta-introducer. Then keys validated by the signed key appear valid to you.
For example: You imported the demo key from the "Sharing Public Keys" article, and also imported My public key from the keyserver. At this point if you were to sign my key and set it as a trusted introducer, then the demo key would become valid even if you have not signed it yourself.
