Recomendo o seguinte para iniciar:
1-) a apostila da Caelum
2-) algum livro de autor brasileiro (procurando bem é possível encontrar alguns livros nacionais bons)
3-) o livro Use a Cabeça! Java
E cadastrar-se no site do Deitel e fazer o download dos códigos de exemplo do Java How to Program. É um arquivo compactado de 75MB. Conforme aprende um assunto novo, procure o capítulo correspondente e então use um IDE para executar e depurar os códigos. Não use um editor simples pois tem muito comentário nos códigos e dificulta a leitura e não dá para depurar.
Não recomendo:
1-) Java Como Programar - muita informação, muito texto, muita explicação, progresso muito lento. Ao contrário de muitos, não considero esse livro avançado e nem um livro de referência. Se tiver, ótimo. Se não tiver, não compre.
2-) Big Java pois segue a mesma linha do Java Como Programar, mas é um pouco menos maçante.
3-) Java Core (também do Cay Horstman) - para iniciantes é tão “pesado” quanto os 2 anteriores, sem a parte final de exercícios.
4-) se está iniciando não é hora de se preocupar com livros sobre a certificação.
Atualmente tenho preferido livros em português, mesmo não precisando de dicionário para ler os livros em inglês. As traduções não são excelentes, mas também não atrapalham. Tenho notado traduções melhores, acho que o pessoal de TI reclamou bastante das traduções grosseiras que disponibilizavam.
Livros em português proporcionam leitura mais rápida e menos cansativa já que o cérebro fica focado no assunto que você está lendo e não precisa invocar um “protocolo” para fazer a tradução.
Os originais em inglês também têm erros, mas são erros nos códigos, erros de digitação e erros em figuras.
Boa sorte!