Some good places to start Android game programming.

I won't recommend Java for writing Android games. Not only because C++ is my native language, but also because of performance concerns and easy portability. However, existing documents about developing Android applications with C++ are rare and brief. Here are some good resources I found:

The official NDK doesn't support many C++ features, such as exception and STL. Although you can solve this problem by compiling STLPort, you may also want to check out CrystaX NDK. This one has everything you need to write a C++ program for Android. http://www.crystax.net/android/ndk-r4.php

Game related libraries can be found here http://code.google.com/p/rokon/ and here http://www.badlogicgames.com/wordpress/. The Rokon engine was the one I used to write the first version of Tower Commander. But at that time, this Java engine was buggy. Later, I quit using it to embrace C++. Badlogic Games seems to be the official site of the game engine libgdx. That website has a lot of things about Android game developing. At least the physic engines of these two libraries are now using C++.

To use Android NDK, you will have to get yourself familiar with jni. There are few good open source projects out there that has examples for almost every jni features. The first one is the SDL port for Android: https://github.com/pelya/commandergenius . You can learn how to write Android.mk from this project. And of course, if you are familiar with SDL, starting your game from this project is a good idea. Also, the kwaak3 project http://code.google.com/p/kwaak3/ is a quake 3 port to the Andorid platform. It is also a very good textbook of learning jni and the NDK.

Replica Island is also worth mentioning, if you intend to start your game with Java. http://replicaisland.net/  This is so far a very good, if not the best, platform game on Android.