"Signing a key" really means signing the binding of a uid to a public/private key pair. I had to look at the Open PGP spec to figure that out ;-)
The question is, how to do verify that a particular person is exclusive owner of a uid? Because the uid is just a piece of text, there is no general way that will work every time. It depends on what the uid is. Someone could put their Passport number in the uid and you could check the passport to verify that they own it.
Of course most people use an email address as a uid. There are some key exchange protocols that will give you a pretty good idea that someone controls an email address (although they may not be exclusive owner). Basically you email them with some information and then they email you back with an encrypted version of that information. While they can spoof sending the email, they can't easily receive the original information to encrypt it.
Generally speaking, online, email uids are what is most useful. You need to know that the person who sent the message has access to the email address in the uid. But if you are actually concerned about the identity of the person, passport numbers, etc are better uids.
A key can actually have many uids. You can add new ones at any time. But if you do, you need to get people to sign the new uids (because while they may trust that you control one uid, they still need to verify that you actually control the other uid).
How you decide that the uid is owned by the owner of the key is up to you and you are free to sign or not sign any key. The web of trust comes where someone else has signed the uid on a key. There is a kind of second order level of trust with that signature. If my buddy Fred has signed the uid, and I am absolutely sure that Fred will never sign a uid without making sure that it is owned by the owner of the key, then I will probably trust it. But if my buddy Carl signs it, I might think "Carl is not diligent enough to check it out", so I might not trust it as much. How you assign trust of third parties to sign appropriately is up to you (and you do it for each of the third party keys that may have signed something).
I hope that helps!