Java is a good place to start since, as you noted correctly Android apps are programed in Java.
how and where to start really depends on your programming experience. if you have never coded anything then you're probably going to want to grab a book that focuses on teaching the basic concepts of programming (variables, functions, strings, program flow, etc, etc). The most ideal book for your case would be one that does that through Java (since ultimately thats what you want to learn).
if you have experience with programming then I would start with the
Java Website which I've found to be fairly helpful in teaching myself Java.
Once you have a basic understanding of Java (enough to understand Syntax, Classes, Methods, Interfaces, etc) you could start suplementing your learning with the
Android Tutorials to begin to familiarize yourself with the important Android Classes, methods, etc.
I think as a general Strategy you should learn enough Java to begin to understand Android and then use Android as the driving motivation to learn more Java!
Where should I begin..?
