The encryption and signing methods assume that parties can freely exchange the Public Key information. The PKI eliminates the risk of "key stealing": the Public Key can be known to anybody (can be "publicly known"). But there is another risk - when a party receives the Public Key, it should verify that that it really belongs to the proper entity. Otherwise a third party can generate its own Private/Public Key and send the Public Key to the center, pretending that it is the Public Key of the spy. If the center does not detect that this is a fake, it will use that key to encrypt the information it sends to the spy. The spy will not be able to read it (it is encrypted with the wrong Public Key), but the third party that has issued the key pair will be able to decrypt it, as it posses the matching Private Key.
To solve this problem, the Public Keys are not distributed in the "raw form". Instead, they are distributed embedded into Certificates. A Certificate contains the following data:
Certificates are issued by a Certificate Authority - some party that all parties choose to trust. All parties should know the Public Key of the Certificate Authority. Modern Internet applications (browsers, mailers, etc.) have a built-in list of Trusted Authorities (including VeriSign and other similar companies), and have the Public Keys of those Trusted Authorities built-in.
When a certificate is received, the receiving party can verify if it has been issued by a "trusted authority": it checks if the "issuer" name in the Certificate is one of the "Trusted Authorities", and uses the already known Public Key of that Authority to verify the Certificate signature. If the signature is verified, the party can trust that the Public Key in the Certificate really belongs to the party specified in the Certificate Subject.
Very often an intermediate Certificate Authority is used. For example, a corporation can get a Certificate issued by a Trusted Authority, and then it can act as a Certificate Authority itself, issuing certificates for its employees. To enable verification of such a certificate by any third party, the Certificates issued by an Intermediate Certificate Authority are sent together with the Intermediate Certificate Authority own Certificate. The receiving party first checks that the Certificate is really issued by that intermediate Authority (by using the Public Key from its Certificate to verify the signature in the sender Certificate), and then it checks that the intermediate Authority is what it claims to be (by verifying its Certificate using the known Trusted Authority Public keys).