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.
Web of Trust and Trust Models
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).
Bootstrapping Your Web of Trust
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.