If you are just beginning learning programming with Java, Head First Java is a good book which is written in a light-hearted language. Java 2 complete Reference (latest Edition) should be a better choice if you already know C/C++ and want to quickly dive into Java. PM me if you need any Java ebooks.
Java complete reference is just what is says - a reference book. It is not meant for actually learning programming in java. If you are new to programming, then pick up head first java. The complete reference will come handy when you actually start programming
If you are completely new to programming then head first java is good book to start with as a lot of ppl above me have suggested...
If you have some programming knowledge and have done something like c/c++ then i would suggest Just Java 2 as i found it well writen. Its not as elementary as head first so i will only advice it if you have some programming basics.....
I read Core Java 2 from Gary Cornell ( Prentice Hall Pub ). That book was really good if you are already used to programming in other languages. No ABCD basics to programming.
Its a good book...i learnt most of my JAVA concepts from this book....it uses an unconventional approach of making us grasp something....and for me that worked......