In the Setting up keys section I had you "trust" your key. What does that mean? Well, it means you trust yourself to verify people's identities before signing their key. It means I give explicit trust to myself and implicit level of trust to any key signed by my own key.
Didn't catch that? Keep reading...
Implicit trust is the way 99% of PGP trust works. Implicit trust happens when you sign a key. When you sign someone's key, your assigning them an implicit level of trust, and that level depends on the level at which you signed their key.
The reason there is implicit trust is because you explicitly trust your own key (via the "trust" in the setup process), and you implicitly trust keys signed by any explicitly trusted key.
Explicit trust is when you do a
gpg --edit-key on someone's key and then type
trust and assign some level of trust to it. This is not the recommended way to trust other people's key.
So why would you do this? You would do this if you knew someone very well, and wanted to trust keys that they had signed, because you knew they were as careful about verifying keys before signing them as you were. In this event you would assign a level of explicit trust to that person's key. Even in this case you would not want to assign "ultimate" (5) trust, but instead "full" trust (4).
The trust DB can also be used to specifically not trust a key (regardless of signatures found). So, for example of you explicitly trust John's key, and John has signed Fred's key, but you really don't trust Fred even though John does (which is a good time to re-evaluate your explicit trust of John), you could specifically not trust Fred's key by assigning a trust of 2 ("I do NOT trust"), to Fred's key.
Also note that explicit trust is private. While signatures are public and make a statement to the world about your trust of someone, all explicit trust is in your local trust database (or "trustdb"), and on one will ever see it.
Note that there are 4 levels of "signing": (0. I don't know, 1. I have done no checking, 2. I have done casual checking, and 3. I have done very careful checking), and remember these are public values. However, there are 5 levels of explicit "trust,": (1. I don't know, 2. I do NOT trust, 3. I trust marginally, 4. I trust fully, and 5. I trust ultimately), and these are private. Generally it is a good idea to trust only yourself ultimately, and gnupg often does this for you.
The web of trust is a bit more complicated that just the above, but the above is a pretty decent summary. In effect, you can tune lots of variables about how trusted keys effect the validity of keys they sign. You can find all the details at http://www.gnupg.org/gph/en/manual.html#AEN385, but by default the rules are, a key is considered validated if it meets both of the following two conditions: