Now that the free MIT App Inventor for Android has increased in popularity, more people are making their own Android apps to control Arduino and compatibles via serial text commands. However if you don't have a Bluetooth adaptor for your Arduino, another method is to use a Bluetooth-equipped PC and connect the Arduino via USB to the PC.
This procedure has been demonstrated by Instructables member bhaskar4n who shows how this can be done with a python application running on the host PC. The serial text received by the PC's Bluetooth transceiver is processed by the python app and then send to the Arduino via the USB cable. It's a long way of solving the problem, however it works.
However if you'd prefer to have direct Android to Arduino communication - you'll need a Bluetooth device for your Arduino projects, and to meet this need we've released our new Freetronics Bluetooth Shield:
We've made it simple to use - the Bluetooth Shield acts as a serial link between the other Bluetooth device. Furthermore there's a wide range of jumpers allowing you to select which digital pins to use for data transfer, increasing compatibility with other shields. And with our Quick Start guide it's easier than ever.
Our Bluetooth Shield for Arduino is now in stock and ready to ship, so for more information and to order - visit the shield's product page.