I believe there are a number of public keyservers for OpenPGP.
I use Enigmail, an extension for the Thunderbird email client that makes it work with GnuPG, so you can exchange secure emails with anyone using any OpenPGP-based system.
To send an encrypted email with this setup, compose the email in Thunderbird as usual and use the OpenPGP menu item (or toolbar button) to check the “Encrypt Message” option for that message.
When you go to send the email, and the recipient’s key is already in your keychain, Enigmail just asks for confirmation that it’s picked the right key, and the email goes out. If Enigmail can’t find a key that matches the recipient’s email address, it shows various options such as retrieving the key from a public keyserver. You can also load the key in advance, from a keyserver, a file, a web site, an incoming email, the clipboard, etc.
However you get the key, you’ll likely want to verify that it’s legit (unless you met the recipient in person, perhaps). Verifying that a key isn’t a fake can be done in various ways. The key may be signed by people you already trust (i.e. people whose keys you’ve already accepted), or by someone they trust in turn, etc. Or you could call up the recipient and confirm the key signature over the phone, for instance.
Receiving encrypted emails is similarly easy. When you open one (or click the Decrypt button), Enigmail asks for your passphrase, offering to remember it for a period of time if you want, then shows the decrypted message, same as any other email.
It all works pretty seamlessly.
This article suggests that in Acrobat 9, the longer key is easier (!) to crack. Seems like it’s particularly important to use long passwords/passphrases with it.