When you retrieve someone's information from a keyserver to add him to your pgp keyring, that is made through unencrypted keyservers, unless the user uploaded it to https://keyserver.pgp.com/. Even then, since keyservers sync with each other, people will normally add you from http connections, like when using hkp://keyserver.ubuntu.com.
So the whole who adds whom is always in the clear?
Yes, it is more or less consubstantial to the Web of Trust in OpenPGP. In the Web of Trust, you can validate a public key by building a chain of public keys, each signed by the previous public key, from a key you trust (yours) down to the key to verify. This works only as long as you can recover such a chain, mostly by interrogating key servers. In fact, since the WoT is an "everybody is a certification authority" system, you should build several such chains, with no common link, so that all these redundant proofs add up into some decent level of trust in the target public key.
One way to see that is the following: by signing the key of somebody else, you vouch for the link between the identity and the key of that somebody else. You announce to the World at large: yes, this is his key, I verified it. It makes little sense to make such an announcement... without actually making the announcement. By definition, key signing is meant to be public.
PGP's Web of Trust is indeed at odds with privacy. Although "PGP" stands for "Pretty Good Privacy", PGP's Web of Trust was never meant to hide the existence of the relationship between people.
See p. 90, "Avoiding the Web of Trust," of PGP & GPG: Email for the Practical Paranoid by Michael W. Lucas.
If you do the job in a right manner, no:
All this is public, shareable and signed and fingerprinted.
Your provider (or Charles) could even see that you have been exchanged some keys, but could'nt know which one you have really added to your keyring (or even if you add one).
For sample, you could download the entire public keyring from one keyserver but store no key or only one...
If you verify the fingerprint given by third party (by an alternative, trustable way, like paper, phone, fax, sms etc...) of any public certificate, the transport make no matter.
The best recognized way to understand this and grown you personal network, is to participate to key signing party where people exchange fingerprint, showing his personal official passeports and back to home, each of them sign the key of each others...
OpenPGP does not require secure transportation to make sure nobody fiddled with with signatures, as the whole system is based on signatures on your keys which can only be provided by the holder of a private key.
Packets you received from a keyserver could be tampered, but you (or your OpenPGP client) will recognize this when validating the signatures. You cannot trust the keyserver's answer (do you know and trust the owner, anyway?), thus automated signature validation should be performed by an OpenPGP client (and eg. GnuPG does). After this validation, you can trust that every signature has been issued by the private key's holder.
An encrypted connection not only ensures unaltered transportation of data, but also makes sure nobody can see what you're transmitting. Without one, any "man in the middle" can see who's keys you're transmitting.
The point of the web of trust is that you physically meet up and verify someone in real life at a keysigning party. The idea of which is the number of personally verified keys lends credence to other keys, hence the web.
