Meine Empfehlungen lauten wie oben Java ist auch eine Insel, Handbuch der Javaprogrammierung und, darauf bin ich die Tage selbst aufmerksam geworden, Head First Java aus der selben Serie wie oben genanntes Head First Design Patterns. Wobei meiner Meinung nach das Buch über Design Patterns erst nach einem fundierten Einstieg gelesen werden sollte, weil es Java-Kenntnisse vorraussetzt und somit für Einsteiger nicht geeignet ist (Habe es quergelesen und würde es einem Einsteiger nicht empfehlen).
Des Weiteren gibt es noch das sehr gute Buch von Bruce Eckel: Thinking in Java. Das gibt es ebenfalls kostenlos zum herunterladen, einfach mal eine Suchmaschine bemühen. Nachteil, es ist in Englisch, Vorteil, es ist saugut.
Ansonsten kann man auch immer noch auf das kostenlose Java-Tutorial, findet man bei Sun auf den Seiten im Download, empfehlen und, was IMMER ein Muss ist, unbedingt die API herunterladen und immer schön alles nachschlagen und lesen. Man lernt eine Menge dabei.