While I agree with the general consensus that
How To Brew is the best choice for a new brewer, I would give nearly equal standing to the venerable
Complete Joy of Homebrewing, especially now that the fourth edition has come out. While Palmer's book is better written more technically accurate, Papazian brings to the subject a creativity and an infectious enthusiasm that is hard not to enjoy.
I also still hold that Dave Miller's books are good for intermediate and advanced brewers, though most of them are now quite dated. The same holds for
The New Brewing Lager Beer by Noonan, and
Principles of Brewing Science by Fix.
Brewing Classic Styles and
Designing Great Beers are both highly recommended, the former being a good introduction to the styles and who to brew them, the latter a more in-depth and technically masterful continuation on those themes.
The often overlooked
Classic Beer Styles series has several gems, and could use more recognition, even if most of them are quite old now.
The Elements of Brewing series are excellent resources for intermediate brewers moving towards more advanced study, and have much to teach even the most experienced homebrewers.
Finally, Stan Hieronymus' books are all well-written and technically superb.