The key needs to be verified. If you trust that someone's public key does in fact belong to that individual and they are in your keyring you can use your private key to sign your correspondent's public key and validate it.
So you are Bob and you trust that Alice's public key does in fact belong to Alice, so you sign it with your private key. So Alice's key is trusted to you. Also any keys that Alice trusts, say someone called Chris will be in your web of trust also. So you can also trust Chris, because Alice does. So Chris’s key will be certified with a trusted signature.
Now if Alice trusts that your key does belong to you then she can validate your public key with by signing it with her private key, therefore your key will now be included in that same web of trust.
a procedure was given to validate your correspondents' public keys: a correspondent's key is validated by personally checking his key's
fingerprint and then signing his public key with your private key. By
personally checking the fingerprint you can be sure that the key
really does belong to him, and since you have signed they key, you can
be sure to detect any tampering with it in the future. Unfortunately,
this procedure is awkward when either you must validate a large number
of keys or communicate with people whom you do not know personally.
GnuPG addresses this problem with a mechanism popularly known as the
web of trust. In the web of trust model, responsibility for validating
public keys is delegated to people you trust. For example, suppose
Alice has signed Blake's key, and
Blake has signed Chloe's key and Dharma's key.
If Alice trusts Blake to properly validate keys that he signs, then
Alice can infer that Chloe's and Dharma's keys are valid without
having to personally check them. She simply uses her validated copy of
Blake's public key to check that Blake's signatures on Chloe's and
Dharma's are good. In general, assuming that Alice fully trusts
everybody to properly validate keys they sign, then any key signed by
a valid key is also considered valid. The root is Alice's key, which
is axiomatically assumed to be valid.
Trust in a key's owner
In practice trust is subjective. For example, Blake's key is valid to
Alice since she signed it, but she may not trust Blake to properly
validate keys that he signs. In that case, she would not take Chloe's
and Dharma's key as valid based on Blake's signatures alone. The web
of trust model accounts for this by associating with each public key
on your keyring an indication of how much you trust the key's owner.
There are four trust levels.
unknown
Nothing is known about the owner's judgement in key signing.
Keys on your public keyring that you do not own initially have this
trust level.
none
The owner is known to improperly sign other keys.
marginal
The owner understands the implications of key signing and
properly validates keys before signing them.
full
The owner has an excellent understanding of key signing, and his
signature on a key would be as good as your own.
A key's trust level is something that you alone assign to the key, and
it is considered private information. It is not packaged with the key
when it is exported; it is even stored separately from your keyrings
in a separate database. The GnuPG key editor may be used to adjust
your trust in a key's owner.
Read more here
Also have a look at this awnser from Server Fault
