Getting a Bluetooth chip to communicate with Android Smartphone
You can essentially use any Bluetooth device that supports SPP (Serial Port Protocol). Some of the most popular are RN-42 based boards like the Bluetooth Mate Silver. A lot of these are advertised as serial port replacements (UART in on one side - UART out on the other). 

On the android side things are relatively simple, although there are some inconsistencies between Android versions. When starting, my approach was to adapt the BluetoothChat sample application. This should be available when you have installed the Android SDK under samples/[platform version]/BluetoothChat. The only trick is to make sure you use the UUID specific to SPP: 00001101-0000-1000-8000-00805F9B34FB

The hardware side is extremely easy - just hook your Bluetooth module up to your microcontroller via the UART and switch the power on. If you need more help on the Android side I found the Android StackOverflow an very useful place for Bluetooth help.