Si el juego va a ser medianamente complejo te aconsejo que te olvides de Java y lo hagas en NDK (C++), para ello te recomiendo la librería SDL para Android:
http://www.anddev.org/sdl_port_for_a..._16-t9218.html
Lo bueno que tiene el SDL es que es una librería portable destinada a la programación de juegos, aunque algunas veces se use también para otras cosas, puedes controlar todos los elementos que se dibujan en la pantalla, el sonido y los controles de una forma bastante sencilla, hay montones de tutoriales en la propia página de SDL:
http://www.libsdl.org
Encontrarás muchos ejemplos de juegos que te compilarán directamente en Android (una vez instalada y configurada la librería, que te advierto que no es fácil).
Si aún así prefieres programar en Java hay motones de tutoriales de programación de juegos, donde aprenderás lo básico de como pintar en la pantalla y como capturar las pulsaciones de pantalla o botones. Sabiendo eso lo demás no es diferente de cualquier otro tipo de programa. Lo que ocurre es que programando en Java tu juego estará más limitado de recursos.