My favorite Linux book for beginners is still Robin "Roblimo" Miller's Point & Click Linux!. This 2004 book may be out of date, and the copy of MEPIS Linux that comes with it is several generations behind the times, but Robin does a great job of explaining exactly what you need to know to get to work with Linux. It's still the best beginner's book out there as far as I'm concerned.
If, like a lot of people, you're interested in learning about Ubuntu Linux, then the best book for you is Mark Sobell's A Practical Guide to Ubuntu Linux (Versions 8.10 and 8.04). This book takes you all the way from the basics to intermediate system administration. What I like about it is that it includes numerous real-world examples and JumpStarts, which are well-written, how-to guides. The second edition, which covers Ubuntu 8.10, just came out and, based on my quick overview, is as good as the first edition.
Ubuntu for Non-Geeks, 2nd Edition, by Rickford Grant, is also an excellent book. Unlike Sobell's volume, which is one of those fat, everything and the kitchen-sink computer books, Grant focuses on making it fun for beginners to learn Ubuntu Linux. If you're just an ordinary user, who's not sure what's going on behind Windows or Mac OS X's glossy interfaces and you don't really care either, this is the Ubuntu book for you.
If you do know what's happening under the hood of your PC, and you need to pick up RHEL (Red Hat Enterprise Linux) for a job, then Christopher Nergus' Fedora 10 and Red Hat Enterprise Linux Bible is the volume you should be buying. It, and its predecessors, doesn't make Linux as easy to approach as the others. On the other hand, if you're going to be working in an office with Linux, chances are it's going to be RHEL or one of its cheaper twins like CentOS. In that case, this, or one of Sobell's older books on Fedora and RHEL, is a must. Another book, in the business Linux line that I recommend, if you're working in a Novell shop, is OpenSUSE 11.0 and SUSE Linux Enterprise Server Bible.
Finally, if you like the Dummies books, the best of this series' Linux books remains Dee-Ann LeBlanc and Richard Blum's Linux For Dummies 8th Edition. It's a bit dated, but it does do an excellent job of holding your hand as learn how to make Linux work for you.
No matter what book you get though, the absolute best way to learn Linux is to use it. Get a book and sit down with it and a computer already running your Linux distribution of choice and start playing with Linux. You'll find that learning Linux really isn't that tough after all. Have fun!