This project shows how connect an Android phone to an Arduino with the Bluesmirf Bluetooth module. The demo can control an led and read a potentiometer. It should work with Android 2.0 (ecliar) and above.
The Bluesmirf Bluetooth module is available from Sparkfun.
Source code is available at https://github.com/jeffboody/bluesmirf-demo