Rodolfo,
Bem vindo ao fórum GUJ, aqui você encontrará um pessooal fera em Java para lhe tirar dúvidas. O pessoal é muito bom e sempre estão a disposição para nos ajudar, digo isso por experiência própria.
Quanto ao Livro do Deitel, ele é muito bom, tem até um exemplo de chat tipo MSN com ele. Também tenho essa edição, que é a mais atualizada. Mas não sugiro começar com ele não.
Também não sujiro começar com a apostila da Caelum, apesar de muito boa. Digo isso por que a apostila da Caelum já começa com orientação a objeto, e isso pode ser um pouco traumático para quem está começando com Java e também começando a programar.
Estudei os primeiros passos com um livro da editora érica, que é muito bom para quem está começando. o nome dele é:
“Java2 ensino Didático. Desenvolvendo e Implementando Aplicações”
Editora Érica
Sérgio Furgeri
Agora parece que é Java6, Desenvolvendo e implentando Aplicações.
O livro dá uma boa embasada nos conceitos fundamentais, um capítulo sobre orientação a objetos, mas sem se aprofundar muito no tema.
Estude com ele, depois você pega a apostila da Caelum e o livro do Deitel.
Essa é minha sugestão.
Qualquer dúvida, poste aí.