There's another possibility to get rid of the warning. If you don't sign the key, but you signed other keys and told GnuPG you trust those others (to only sign keys they are sure of) and the owners of those keys have signed the questionable key, GnuPG will accept it as being authentical. How many signatures exactly are needed, is configurable and depends of the amount of trust you assigned to these others.
The latter mechanism can be used to build a ``web of trust''. If you have some friends you know to be careful about signing keys and you know to have the real public keys of them, you may allow them to introduce new trusted keys to you.
Apart from this model, you may also use an hierarchical key signing policy. In a company, you may designate a person responsible for signing keys and the user may trust all public keys signed by this one. There are also Certification Institutes (CA) that sign keys, if you prove your identity with the help of a passport. Depending on their published policy, their owner, their visible skill and your paranoia, you may trust keys signed by them.
Note that you can also have untrusted keys in your keyring. You will be warned, when using them, because you don't know, those really belong to the one they seem to.
A lot of people just store their public key on a web site or submit it to one of the public keyservers. See http://www.keyserver.net/ or http://www.openpgp.net/ for more information on keyservers. Putting your gpg key into the file ~/.plan is also a good idea: People can get it by a finger command. Printing your key's fingerprint on your business cards is also a nice idea.