As is typical for questions about fitness, this question has more than one valid answer.
The essential question @AndrewSalmon is answering is the right one:
"If evolution eliminates disadvantages, why can xyz trait still be seen the population?"
Here is a more complete list,
1) The trait is not eliminated by evolution since it is manifested after reproduction. The classic example of this sort of trait is senescence. Why do we grow old and die? Clearly it doesn't stop us from having offspring. I generally don't find this sort of answer informative. Its not a bad argument for the traits of bipolar and schitzophrenic tendencies which can manifest as a chronic mental condition, often in the 30s after many people have children.
These traits are fairly common (1 in 6) in the population.
It is usually arguable that these traits are of some sort of advantage from some perspective (including my examples). In this case @Andrew argues this. I'm not sure I agree, but you can read his post for the argument.
2) Pleiotropy. The idea that the negative trait evidences more than one trait. In this case one might say that baldness is tied with another trait that is beneficial. Some say that the cause of male pattern baldness, which is an excess of testosterone, would be tied in with other masculine signals, which can often outweigh disadvantages of being bald and trying to find a mate. A trait like baldness could also for instance be tied to a desirable trait in women, causing it to persist in men as a result of the advantage of say, less hairy women. I probably wouldn't take this stand either, though its conceivable.
3) "Neutral variant" The third explanation that I will put out is that baldness simply isn't a trait with enough disadvantage (if any) that it should be removed from the gene pool. While there is evidence that baldness is a disadvantage come friday night, to say that a trait is disadvantageous we have to see, in the long run - over the lifetime - really is a disadvantage. I think I would agree with those who say that while some women do not find bald men attractive, its not enough to stop them from having kids, which is all evolution cares about.
And if you happen to be balding probably what you should care about, guys!
If evolution should eliminate male baldness, then why not eliminate sterility, homeliness, impotence, poverty, obesity, being dull, living with your parents and adolescent awkwardness? These are probably even more important obstacles to finding a mate? All of these traits are beneficial traits that are maladapted to modern life or genetic accidents. Evolution can't get rid of them at all I think.
For an even more complete discussion of the general subject, see Dawkin's "The Extended Phenotype". Baldness is not discussed however.