My policy for signing OpenPGP keys is strict. I may locally sign your key based on lesser constraints, but that will always remain on my computer only.
Meeting in person. If I stumble accross you, and either know you or get to look at an acceptable proof of your ID, I am willing to exchange fingerprints for signing.
Phone call. I am usually willing to sign your key after a phone call in which we exchange fingerprints, provided that (TBD -- I know you and recognise your voice?).
Secure website. If I find your fingerprint published on a website secured by a website certificate that I trust, I will sign your keys for all email addresses (user IDs) under that website. This is because the website can be authenticated as belonging to the owner of the domain under which your email address resides.