Te recomiendo "way of the android cracker", yo recién me inicié con eso. A grandes rasgos lo que se suele utilizar es dex2jar para pasar el .apk a .jar, con JD-Gui se lee el .jar y se tiene un código en alto nivel (java).
Así puedes hacer una vista general del programa, y entender las cosas mejor, ya después para modificar usa apk-tool (con los comandos que te comentan en el tutorial), y lo pasas a .smali el codigo, y ahí ya puedes cambiar lo que te plazca, pero tienes que entender el dalvik bytecode pero por ahí en el tutorial había una lista.
Por lo demás vuelves a compilar, firmas, e instalas el .apk modificado.