SparkFun's IOIO
Mike Green
Posts: 23,101
Here's a good summary of what SparkFun and Google are doing in terms of Android support for hardware hacking. A Propeller could certainly be made to interface to one of these evolving interface APIs.

Comments
http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=2919¶m=en546067
I have a propeller based vending machine interface that I designed that utilizes wireless connectivity to an Android device. The hardest part was writing the Android code to communicate with it.