Actually, the naiive approach of just grabbing a key from a keyserver isn't vulnerable so much to a man-in-the-middle attack as to a poisoning attack.
In a poisoning attack, an attacker provides an alternative piece of information, in this case a public key, and somehow tricks you into using that instead of the real one.
In a man-in-the-middle attack, the attacker sits (logically or physically) between you and the system, or recipient, you're talking to, appearing to each end point as the other end point.
That said, you are correct that keys from a key server cannot be trusted immediately. They do need to be validated somehow.
In the PGP/OpenPGP/RFC4880 trust model, that validation is primarily via key fingerprints and signatures.
For the sake of an example, let's say Alice wants to communicate securely with Bob, but neither of them have ever met, nor is it likely that they will be able to meet. Both, however, have access to an OpenPGP implementation and can upload public keys to key servers. Both have gone through the preliminaries of setting up e-mail accounts, creating key pairs associated with those e-mail addresses, and uploading their respective public key to a shared key server.
So can Carol, who would like to be able to read what Alice and Bob are sending to each other. Carol has also somehow gained access to Bob's e-mail account. (Maybe Bob used a weak password.)
The easy way, if Alice is able to communicate with Bob out of band, is for Alice to contact Bob using some other medium, and ask him for his public key fingerprint. If that matches the key that Alice has, and Alice can trust that the person responding is actually Bob and not Carol, then she can very likely trust the key to belong to Bob.
Even if she can't, however, there is a way.
Bob isn't alone in this world. While Alice can't meet Bob in person, a number of other people can and have. Those people can sign Bob's key, which is a statement that they have verified Bob's identity, and that the key they are signing actually belongs to Bob, and not to an imposter. Carol can't get those people to sign her key as belonging to Bob, because that would raise questions on the form "hey Bob, why're you changing keys?", ideally asked in ways Carol cannot control. For example, Dave might pull out his phone book and call Bob on the telephone to ask, since he recognizes Bob's voice, or might ask him at work, because they work for the same company.
So Alice can look at the set of signatures on the key purporting to be Bob's, and then the set of signatures on those keys, and so on. The purpose here is to trace the signatures back to a key Alice trusts, either because she has verified it herself, or because it's a widely trusted key in the community. (For example, the widely distributed official key of the creator of the software, or that of someone associated with a large free software project, can likely be trusted if its fingerprint can be verified.)
Why not just look at the signatures themselves? For one thing, nothing prevents Carol from creating keys and signatures that appear at first glance exactly like the signatures on Bob's actual key. But while Carol can create a trust chain among the keys she create herself, she cannot anchor that trust chain elsewhere. So the trust chain might eventually lead to a key purporting to belong to, say, Werner Koch or Phil Zimmermann, but Carol can't actually anchor the trust chain there because presumably Werner Koch or Phil Zimmermann are very careful about verifying the identity of the owners of the keys that they sign, and the keys that the trust chain leads to wouldn't match their official keys. Finding a chain of signatures leading back to a high-profile key which can be validated as belonging to that individual means it is very likely that the key one started out with has not been falsified.
Alice can also ask others for the fingerprints of those anchoring keys. If multiple people agree that Koch's key has a certain fingerprint, and this matches the one she has, that significantly increases the trustworthiness of Alice's copy of that key.
Yes, there is a fair bit of work to be done if Alice wants to do this properly. That's the price one has to pay for not having a set of super-trusted keys at the root of every trust hierarchy, the way the TLS CA ecosystem (as used by web browsers) works. The flip side of that coin is that every user can decide which keys they actually trust to sign other keys.
Once Alice has verified that Bob's key is legitimate, she'd usually sign it locally (add a non-exportable signature of her own) to it. It'd be non-exportable because she hasn't actually verified the identity of the key holder, so she doesn't want to tell others about that and thus degrading the trustworthiness of her actual key signatures, but she does want to indicate to herself and to the software on her system that she has done some degree of verification of the key, thereby silencing any "this key isn't trusted!" warnings.
Simple, isn't it?
