> but then again I know nothing > about android...
An APK is more or less just a renamed ZIP, with a specifically-laid-out tree of assets as well as libraries and binaries. As such, it's in fact especially easy to transparently replace the existing libraries in an APK with ones that are malicious.