The people at the Mitchtech blog have published a useful article about controlling Arduino digital outputs using an Android phone via the Arduino+USB host shield combination. The neat thing about the tutorial is that the author has written in a style to make it as simple as possible, instead of trying to be too clever. In no time you'll be controlling digital outputs and increase your confidence to move further along. They use the "microbridge" Android Debug Bridge (ADB) implementation for microcontrollers, so check it for compatibility with your phone before getting started.
Apart from being a fully Arduino Uno-compatible, it has onboard microSD socket and the full USB socket and host-mode controller. As well as the Bluetooth application described above, this is the ideal platform for developing peripherals or projects based around Android devices with ADK (Android Developer Kit) functionality, but without requiring a USB host controller shield stacked onto an Arduino. For more information and to order, visit the product page here.