El libro de Deitel&Deitel es bastante bueno para empezar (solo he usado el de inglés, pero se que existe en español también), haga todos los ejercicios y si puede pídale a alguien que se los revise (es fácil pensar que uno está haciendo algo bien porque funciona, pero puede estar agarrando mañas o haciendo cosas ineficientes).
La mejor manera para aprender es tener un proyecto que lo motive a avanzar, ya que hacer ejercicios solo porque sí se vuelve aburrido. Le recomendaría que lea un poco sobre RoboCode , es un juego/plataforma en Java donde ud programa las acciones de un tanque y los pone a pelear con los robots de otra gente. Probablemente no le vaya a ir muy bien al principio (ya que hay gente que aplica temas avanzados de IA) pero si tiene amigos de nivel parecido se convierte en una competencia interesante.
También podría considerar buscar un framework/motor en Java para desarrollo de juegos. Le quedo mal con ejemplos, pero de fijo hay, solo busque reviews y trate de encontrar alguno que sea fácil de usar y le maneje bastante de las cosas por atrás. Una vez que tenga más dominio del idioma, y todo lo que implica un motor, puede tratar de programar uno propio, inclusive.
Si prefiere ejercicios cortos generales, puede entrar a Project Euler o UVa Online Judge, tienen varias pruebas que puede hacer y si no me equivoco ahí mismo tienen un bot que revisa que sean correctos. Este tipo de programas son los que suelen utilizar en las competencias de programación en niveles de pre-grado (al menos los de dificultad media/avanzada).
En general hay mucho recurso en internet, es solo de sentarse a buscar.
GLHF!