PGP is designed to use a "web of trust" to authenticate public keys. There is no central authority (like a CA) for PGP, so you need to have other people sign your key.
To validate a key, you compare how much you trust the people who have already signed it, with how much you trust them. If you see only one signature, and it's from nobody you know, then maybe you shouldn't trust it much. But if it's signed by five people, and one of the signers is your boss, you would probably trust it quite a bit.
Web of trust -- signing
Key signing is important to PGP, but it's hard to understand at first.
When you sign a key, you consider two factors: how well do I know you are who you say you are, and how much do I trust you to check other people out before you sign their keys?
If you were my best friend, I would attest that you are without a doubt Martin. But I don't know you at all, so today I wouldn't sign your key. Now, let's say we met at a conference, and you asked me to sign your key. I'd ask you to show me your driver's license first. I'd sign your key then, with a level that matches my confidence that your license wasn't forged.
But I still don't know you as a person. I don't know if you're responsible type or not, so I wouldn't place any trust in your ability to be careful when checking out other people. But my best friend is a very careful person, and I would also trust him to check out other people very carefully before signing their keys. So I would sign my friend's key and attest that my level of confidence in him is very high.
Web of trust -- using
So now you have a public key from someone. How do you trust it is actually their key? You look at the signatures. You look at who attested to the authenticity of this person. Are those signers people you trust? Are they famous people? Are they just random strangers? Did the signers place a lot of trust in the key, or just an acknowledgement that they signed it. If the signers are people you trust, you'll quickly accept it. But random people? Maybe you can trust it if enough of them signed it. And that's where you set your threshold level of trust. You'll trust a key that your best friend signed. You'll trust a key that your best friend said was signed by a good guy, but maybe not one where your friend said "I don't know him well." Otherwise, maybe you'll choose to trust it if it has 10 or more random signatures.
Ultimately, there is a "strong set" of about 50,000 signers who people around the world do trust. If two or three of them have signed a key, it's a strong indication you should trust it, too. People from that group are who you really want to sign your keys in order for members of the public to trust yours.
So now you have some people in your organization you want to entrust with PGP public keys. How do you get their keys trusted? First, have them sign each other's keys. Then, get them signed by others. Lots of others. Post those employee's public keys on your official web site's "contact us" page. What you want is to establish many connections into the web of trust so that many people, some of whom are well respected and trustworthy, have attested that these employees are who you say they are.