"Running Linux," from O'Reilly, is almost the de facto standard to learn/admin Linux. Also, "Linux in a Nutshell" (also from O'Reilly) is a good reference book, but not as much of a tutorial. If you are headed in the Red Hat direction, "Red Hat Linux Unleashed" from Sams is a huge (1100+ pages) book, but does assume you have at least a little experience with the command line, etc. This one is good because there are specific chapters for key server services: DNS, mail, FTP, Samba, firewall, etc.
Another great reference to have, not Linux specific, is the "Unix System Administration Handbook" (Nemeth, Snyder, SeeBass, Hein). Covers Linux, Solaris, HP-UX, and FreeBSD in great detail. Real-world examples and advice, learned the hard way by some veteran sys admins. Not for a total beginner, but once you know a little, this will help you get the rest of it.
Hope this helps -- you can check out the Slashdot book review section as well, and read the comments readers have left for various book reviews to see what many others think about Linux How-To books, etc: http://slashdot.org/index.pl?section=books
