Java言語を独学するための書籍を紹介します。
インターネットにも有益な情報はありますが、ネットは調べるのに便利であっても、黙々と勉強するのにはあまり適していないと思います。じっくりと勉強するにはやはり書籍が一番だと思っています。（特に入門書）

入門書

Javaのみならず、プログラミング言語を初めて学ぶ人向けの良書を2つ紹介します。
初めてプログラミングを学ぶ場合に、2通りの考え方があります。

低レベルなコマンドラインを使って、根本から学ぶ方法

どちらかというと古い考え方で、実際にその低レベルな知識が必要になるかと言うと、通常は必要が無いと思います。知識として知っておくのは悪くないのですが、余計な勉強の手間を増やしてしまうかも知れません。

便利ツールなどを活用して本質的に知らなければならないことを学ぶ方法

根底に存在する知識を知らないまま、モノが出来上がったりする可能性がありますが、学ぶべきことを集中して学べると思います。ただツールが新しいバージョンが出たりすると、その影響を受けてしまいがちなのが問題です。

私はどちらかというと、後者の方を支持しています。その上で2つの本を紹介します。

創るJava

実行結果が分かりやい便利ツールを使って学ぶタイプの書籍です。NetBeansというJava開発ツールを使って勉強します。プログラミングそのものが、目に見える形でGUI（画面）を使って行うので、実行結果が分かりやすいです。
従来のJava入門書であれば、コンソールに実行結果が出力されて演習するわけですが、そういったことよりも遥かに分かりやすいと思います。NetBeans自体はこれから人気がでて主流になっていくと思います。学んでおいて損はないです。
内容そのものはJavaの基本から入出力、DB、Webまで幅広く、一からじっくり学ぶのにオススメだと思います。

2008/01/26追記：
創るJavaは第2版が発売されました。

創るJava 改訂第2版
~NetBeansでつくって学ぶ Java GUI & Webアプリケーション~
NetBeans6.0に対応した改訂版です。作者のきしださんのブログではこんな風に書いてありました。

2008-01-23 – きしだのはてな
アマゾンの商品説明には「NetBeans6.0に対応させた」とありますが、「そんなのおまけです。以下略です。」で、メインは、章立ての見直し、サンプルのやりなおし、深い部分の追加記述、Java SE 6への対応、JPAへの対応、JSFへの対応、ついでにTomcat6への対応です。
ページ数の増加は4ページだけですけど、中身はかなり増えてます。結構別物。初版をもっている人にも2000円分くらいの価値はあるかと。

これから買う人は第2版の方を買ったほうが良いです。

やさしいJava 第3版 やさしいシリーズ

図が分かりやすいこちらはコマンドラインを使って学ぶタイプの書籍です。
「やさしい」というタイトルをつけているだけあって非常にやさしいです。他の書籍で2,3ページで軽く説明するような内容を、5~10ページ使って説明してあるので、他の書籍で理解できなかった人にもオススメです。
文中で使用している言葉も「やさしい」のが特徴です。変数やオブジェクトの参照を表す挿絵も非常に分かりやすいと感じました。
一方、文法を学ぶというのがメインなので、これだけでは仕事で役立つところまでは持っていけないと思います。

普通ならばわざわざ図を書いてまで説明しないことまで、図が用意されているので本当にプログラムを知らない人に説明する場合には重宝します。（例：代入をわざわざ箱で解説してあったり、ifの条件式を図で書いてあったりする）
しかし、内容が少しC言語的な書き方であったりするのが、少しJavaっぽくないとも感じます。

まとめ

2つの書籍を比較して、私が特に推薦するのは、「創るJava」です。
GUI画面を使って結果を確認できるので、プログラミングをしたことがない人にとっては、「ああ、プログラムを作るとこういう結果が出せるのか。」ということが目に見えて分かると思います。
開発ツールNetBeansを使うのは良いのですが、やはりバージョンアップによって記事が古くなってしまうのが問題です。書籍ではNetBeans4.1をベースに記述されていますが最新版は5.0です。本質的なところは変わっていないはずですが、初めて学ぶ人にとっては大きな障害になるかもしれません。
非常に惜しいことですが、最新版を使わず少し古いバージョン4.1を使えば、全く問題ありません。

教えるための教科書としては、「やさしいJava」の方が向いていると思います。
余計な環境に左右されないうえに、分かりやすく書いてあるため万人向けだと思うからです。