Suppose Alice wants to find Bob's public key. There are several possible ways of doing this. She could call him up and ask him to send his public key via e-mail. She could request it via e-mail, exchange it in person, as well as many other ways. Since the public key is public knowledge, there is no need to encrypt it while transferring it, though one should verify the authenticity of a public key. A mischievous third party could intercept the transmission, replace Bob's key with his or her own and thereby be able intercept and decrypt messages that are sent from Alice to Bob and encrypted using the ``fake'' public key. For this reason one should personally verify the key (for example, this can be done by computing a hash of the key and verifying it with Bob over the phone) or rely on certifying authorities (see Question 126.96.36.199 for more information on certifying authorities). Certifying authorities may provide directory services; if Bob works for company Z, Alice could look in the directory kept by Z's certifying authority.
Today, full-fledged directories are emerging, serving as on-line white or yellow pages. Along with ITU-T X.509 standards (see Question 5.3.2), most directories contain certificates as well as public keys; the presence of certificates lower the directories' security needs.