Hi, I'm kind of starting too, but I’m on pg 200 of about 600 in a book called Head First Java 2nd Edition (O'Reilly Series). I'm not sure, it's very possible that they have a new version out. Mine is from 2003, I got it at Boarders a couple weeks ago.
Head First Java:
-Lots of Content
-Easy Reading (not like a text book, I read about 20-30 pgs at a time you don't get bored)
-Good for people w/ a little programming experience (I took a year of Programming in C before this, some of the stuff was review for me, but it's tons of new stuff too)
You demonstrate that, although many people like Head First, different people like different books. I happen to like the Deitel books, but I know other people don't. I think as a beginner you will find the "How To" books better value for money than the "for programmers" books. I also think you may find the 6th edition of the Java book second-hand for much less than its new price.
I recommend you go for books which introduce object orientation early (Deitel and Head First do; Dummies and "in 21 days", at least in the copies I have, don't).
Also have a look at our book review pages under "beginning Java".