Joy of Homebrewing (aka JOHB), by Charlie Papazian. The seminal work. It is vital to understanding the spirit of homebrewing, although some of the techniques are not the most modern. So read it for the feel. This is the origin of RDWHAHB ("relax, don't worry, have a homebrew"). Since some of the techniques are dated, this is a great book to get in old edition, used, etc.
How to Brew, by John Palmer. This book is a fantastic second book after JOHB; it provides modern technical and procedural guidance the way that JOHB provides philosophical guidance. I got this one free with my AHA membership, but it is worth your money.
New Brewing Lager Beer, by Noonan. Terrific technical information, useful to all brewers (not just lager brewers as the title might suggest).
Big Book of Brewing, by the late Dave Line. Dated and UK-centric, but you might find a used copy fer cheeep.
Beer Captured, by Tess and Mark Szamutlski. I don't really like recipe books. I'd rather use the net. So this is more of a personal use issue than any reflection on the quality of the work.
Yeast Culturing for the Homebrewer, by Rog Leistad. Almost a pamphlet, its one of the few non-professional sources of yeast culturing reading for the homebrewer. Most yeasty books are for microbiologists and cost over $100.
Homegrown Hops, by David R. Beach. Looks self-published and rough, but before the interwebs this was one of the few books on growning backyard hops.