I wanted to recommend a couple of great books to get people started learning Android (of course, you could just skip the books and just use some of my tutorials including source code ;)
This is a nice introduction to the Android platform - walking through from simple applications (as you may guess from the title!) through to some more complex topics such as working with Android's built in SQLite DB and OpenGl Graphics.
Note though that the book isnt a Java book (as none of these here are), and whilst its an introduction to Android, its not an introduction to the wider Java language structure/syntax - so will assume an understanding of the background.
Beginning Android Games
A great book to get started with Android game development! One of the nice things about this book is that it a more hollistic walkthrough of mobile game development and covers more general topics and issues for the area, whilst also providing specific Android examples to try out, it should give you a firm grounding in Android Game development.
The one thing to note that whilst this book does give you an excellent base in game development, it doesn't cover any of the great libraries currently existing for game development such as AndEng, libGDX, Rokon etc
Pro Android 2
This book is actually in its third edition now, but I only have the second edition, so I will link that here - although edition 3 is probably also a good shout.
First thing to mention, don't be fooled by the name! Whilst it descibes itself as Pro Android, it is still pretty suitable for a beginner (I found it was anyway, as long as you know Java, XML, etc) - and actually if you are looking for a "Pro" book this may not be the one for you as it doesn't cover all the topics you may expect for a pro book - such as use of the accelerometer and physics engines. That said, it does provide a solid covering of core topics needed for Android development right through from UI/Menu design through to also covering 2+3/D graphics.