PGP keyservers

Client↔Server protocols

PGP keys can be retrieved with a variety of protocols; the two dominant ones are LDAP and HTTP. Email and FTP are also used, but are less common. When searching for keys, there are two dominant options: LDAP queries and HTTP queries by some format. So while HTTP keys can be retrieved from any arbitrary URL, something a bit more structured is used to search and, commonly, retrieve.
There is a higher-level protocol above HTTP called the “Horowitz Keyserver Protocol”, or “HTTP Keyserver Protocol”, or just HKP. This specifies a specific default port number (11371) and a local URL name-space for constructing URLs to retrieve, upload and search for keys.
This page focuses on HKP-speaking keyservers.
The protocol is specified in Marc Horowitz's thesis paper and an expired RFC draft by David Shaw, draft-shaw-openpgp-hkp-00.txt.

Server↔Server protocols

Given some set of PGP keys which have been made publicly available, there is utility in making these propagate to be retrievable from any keyserver; this is normal and routine.
There are two common protocols for distributing keys: email and SKS. Email results in any keyserver retrieving an update to send that update out by email, remembering the update and removing it from being sent twice to the same host. In some implementations, the keyserver only sends out emails for keys directly uploaded to it, not for keys received from other servers, which avoids loop-detection issues but results in patchy distribution of updates.
The “Synchronizing Key Server protocol”, SKS, comes from the Synchronizing Key Server keyserver implementation: it is both the name of the protocol and of a specific implementation. This protocol, typically spoken on port 11370, uses a set reconciliation algorithm to determine which keys/updates one server has and the other does not. Having determined which keys each side is missing, each then issues regular HKP queries on the default (11371) port to retrieve those updates.

DNS keyserver pools

There are then meshes of keyservers mutually exchanging keys, and a public set of these keyservers on the Internet open for all. On top of this, spidering tools walk the mesh (finding information out via a statistics page which SKS-speakers make available over HKP) and determine which keyservers are "up-to-date" and publicly available and build DNS pools of those keyservers.
Some increased formality is used when a pool is constructed of HTTPS-speaking servers, to liaise about X.509v3 PKIX certificates used for speaking HKP-over-HTTPS (HKPS) , so that a common certificate authority can be used for a given pool; all HTTPS-speaking servers are expected to support TLS ServerNameIndication to permit selection of an appropriate certificate, with keyservers thus being able to be in multiple HKPS pools.
One consequence is that the easiest way to get keys is by setting up an SKS-speaking server, and the main public pools will only point to SKS speakers which can be spidered.
The dominant pools are maintained by Kristian Fiskerstrand, documented at www.sks-keyservers.net, and I recommend using hkp://ha.pool.sks-keyservers.net if cleartext is acceptable (pool of servers with a proxy in front). Definitions such as keys.gnupg.net are then CNAMEs to pools such as these. End-users should probably configure their client to use a common pool definition alias which someone else can then repoint as operationally necessary, rather than directly selecting a pool (unless they wish to track closely), so using keys.gnupg.net is a good choice which minimizes the need to know or care about backend issues. Large organisations might reasonably configure a name within their own namespace, under their control, and make it a CNAME to a public pool definition.

HKP keyservers

PKS
SKS
Hockeypuck
Skier
thttpgpd
onak
OpenPKSD
CryptNET Keyserver (cks)
Krypton
PHKP