Bluetooth is obvious. You can easily put out serial data to a cheapo BT modem, and pass that off to a microcontroller.
Pros: simple, portable, flexible, not a super power hog
Cons: slow, high latency, flexible -- need to develop own protocol
[Eric Mockler] says: I use Basic for Android and the BT for serial access.
See the bead-sorter project for another example (Droidscript + Arduino).
[MartinR] says: For making Android apps take a look at MIT App Inventor 2 http://ai2.appinventor.mit.edu Totally insane GUI programming but gives access to Bluetooth and BLE.
So many ways to go here, and a Bluetooth serial terminal is always handy...