Java: How to Program
by Harvey Deitel, Paul Deitel

Another book from the masters of Java tech books, the Deitels, the thing we like about this one is the thousands of lines of "live code" that is used to illustrate the concepts. Fully updated for JDK 1.4, if you can only afford one book, this should be it....

Beginning Java 2 SDK 1.4 Edition
by Ivor Horton

Well regarded, mighty tome (1100 pages) from Wrox press. This one takes a very thorough methodical approach, which we reckon will result in a deeper understanding for those with the right patience and mind-set. Recently revamped for 1.4.

Learn to Program with Java
by John Smiley

Don't be put off by the "cheap" presentation, Smiley is a training guru and this book looks to offer very good coverage of core concepts. Unlike other books this one sticks to the central technologies, so other books may be required for related technologies.

Programmers Guide to Java Certification
by Khalid A. Mughal, Rolf W. Rasmussen

Not suitable for learning the language from scratch (the certification exam is specifically designed to require real experience), this book is nevertheless the ideal candidate for programmers who are already proficient or are using the certification as a goal.

Java 1.4 and the Sun Certified Developer Exam
by Mehran Habibi, et al

As the title, implies this book is an ideal companion to other java books that don't cover the developer (not programmer) certification, or JDK 1.4 in sufficient depth.