Do you have prior programming experience in another language? Some books about Java are aimed at those who've coded before but are just learning another language, some are for people who haven't really programmed before. If you fall into the 2nd group like I did, this post may help you out. I only had minor experience in Javascript.
I'm starting college in the fall as a CS major. Since my high school had no CS courses, I decided to get started on my own over the summer. I wasn't sure where to start, but emailed several professors and got some good answers. All but one suggested Java as the language, and most suggested buying the book used in the first Java course at the school.
Suggested book: Java Software Solutions by Lewis & Loftus (3rd edition)
Link:
http://www.amazon.com/exec/obidos/tg/detail/-/0321197194/qid=1089150936/sr=1-1/ref=sr_1_1/002-7579130-7705645?v=glance&s=books
(Click "used and new from..." to get it new for half price or lower.)
Alternative book availible free online:
http://www.mindview.net/Books/TIJ/
(I haven't used it really but you might want to check it out if you're feeling thrifty).
There must be a thousand books about how to start on Java... so it's not surprising that everyone suggests something different in this thread =( I've been doing well with the Lewis & Loftus book. It's definitely not too hard for a beginner, yet there are almost always a couple more challenging Programming Projects at the end of each chapter. And, of course, you can come up with your own projects or modify/build on the ones they give you.
EDIT: It sure sucks when the power goes out and wipes out your original post before you could send it! I need a UPS bad =(