This is what the Web of Trust is for. You aren't supposed to identify the person based on the name (anyone can choose any name), but based on the fingerprint. The idea is that you may have met, in person, someone who themselves has met, in person, and so on. It's like the six degrees of separation, but using cryptography to establish trust. When people go to keysigning parties, or just happen to meet someone at an event, they often sign this person's keys to testify that they trust that they are really who they say they are. After all, if you meet someone in person and they tell you their fingerprint, you can be far more sure that it is legit than if you get the key off of a keyserver.
Hopefully, someone in your web of trust has met and signed a key for someone who, through any level of indirection, has met Max Anderson, leading you to trust him by proxy. This website explains this in more detail. Note however that many people do not use the web of trust and instead rely entirely on the principal of TOFU, or Trust on First Use. This provides a lesser amount of protection, but it does not require getting yourself involved in the web of trust.
So what does this look like? Let's say you and I meet at some event and we sign each other's keys. A few years ago, I met Alice at a keysigning party. Naturally, Alice also knows Bob. Bob used to work for Max Anderson's boss, so he is also in the web of trust. Through this web, even though you only know me and not Alice, Bob, or Max Anderson's boss, you still know that the public key you have is owned by the real Max Anderson. Now of course a real web of trust has redundant links (hence web), letting you know more reliably that the public key you see is the real Max Anderson's.
Here are some other questions and answers which may be enlightening:
