The typical answer from experienced programmers is that one should start with Java before moving on to Android-specific code, but I disagree. I think the most important thing for a new programmer is to be able to see the fruits of their work quickly and in a context that feels useful to them. In other words, you need to have some sort of personal project that you're trying to complete. This gives you more motivation than working on some random program in a textbook, and you learn by overcoming the specific obstacles en-route.
Now I must add that I am not an experienced programmer, and I have never tried to teach anyone to program. In that sense, CommonsWare's comment should hold more weight as he has written multiple books on the issue and thus has experience as an instructor. However, I speak as someone who has taught himself to program in Android-Java essentially from scratch. I had dabbled in a few languages like VB (for Excel macros) and C, but I never wrote anything more than about a hundred lines of code long and didn't know anything about object oriented programming.
Of course, doing things this way will be messy. You'll often read tutorials and be confused by why they are doing things the way they are, or for example, what they mean by a "private static" integer or class inheritance. You'll also program with poor style, solving problems with a clumsy or inefficient manner. However, I think these problems are outweighed by the benefits of personal motivation. It's much easier to study something if you know why it matters to you.
The trick however is to make sure you choose easy projects to start with. You must realise that programming anything useful will appear complicated and difficult. Trying to start with a 2d game will not work; there is just too much to learn first. The best place to start is the tutorials on the Android Developer's website. Work with those and see if you can modify them a bit to do different things.
After that, see if you can find some simple things that irritate you with your phone (note: I'm assuming you actually have an Android phone), or things that would make life easier. In my case, I wrote a few very basic programs to do things like change the volume of my ringtone at one press, to go from silent to mid-volume and vice-versa.
Once you've done that, you can tackle bigger projects. Of course, eventually you're going to have to knuckle down and read the 'proper' Java tutorials as you can't bumble along half-blind forever. But to reiterate the point, I think it's much easier to learn if you know why it matters.
Above all, be patient and persevere! It's fun once you're past the initial bewilderment!