I have found that there are three types of books, depending on your goals. One is the reference type like the O'Reilly books "Java in a Nutshell." Will keep for a long time, but you better know some basics on your own. Another type, (get it), are the 'prepare for the test' books like McGraw Hill "Passport Exam 310-025" or the "Java Certified Programmer for Java2" from Osborne. Both have test disks for practice. Then there are the Sams "Teach Yourself Java in 24 Hours" books. Better know something about programming in another language before buying these. They're fast and light, sometimes too light. Then Sun themselves puts out books like "Core Java, Vol. 1-Fundamentals." These are the best for learning if you know a little something. I use them as a quick reference when ever I get into an area that I know very little about. Good luck.
There are in fact more, there are books that actually teach skills rather than just cram your head full of exam answers :)
Look for Head First Java (Kathy Sierra and Bert Bates) and Agile Java (Jeff Langr), both excellent tutorials that teach you well.
Then there are the books that teach specific topics in depth, which you also forgot to mention.
In general, you should avoid all books titled "teach yourself XXX in 24 hours" (or similar) as they're all rubbish.
Similar with the entire "for dummies" range, which is indeed for dummies and guarantees you'll remain a dummy after reading it.
That pretty much comes to the next point: avoid all books by SAMS and Sybex unless you know for a fact that the author is good (which very few authors publishing at those 2 companies are, Marco Cantu being one of the very few exceptions).