For $8.60, you can buy a very simple Bluetooth serial module that works great with Arduino. It uses 4 pins: GND, VCC, TX, and RX, and has a very simplified configuration of only Name, PIN, BAUD. With a device like this, you can do simple bi-directional serial over bluetooth with a PC or Android phone easily. BlueTerm is an Android Bluetooth Serial Terminal app that works quite well. You can also interface to Bluetooth Serial in native Android applications if you want to easily interface an Arduino with an Android on the cheap (Bluetooth SPP is supported by a LOT of Android devices!)
I wrote this utility to easily configure the NAME, PIN and BAUD of the module. Once they are set, they are stored in firmware and you won't need to set them again.
NOTE: You probably do not want this configuration to be a part of the actual Arduino application - If there is an active Bluetooth connection, these configurations will fail. Better off to just set it and forget it.
This is written to run on a Mega (multiple serial ports), but can probably be modified to run on a board with a single serial port by removing all the logging and just using the single port, but it will be much harder to debug problems, of course. Since you only need to run this once and the settings will be saved, if you have access to an Arduino with a secondary serial port, just use that to configure it and then transfer it to the target single-serial system.
Hope somebody else finds this useful!
Here's a link to the device I'm referring to:
SetupBluetooth.ino (3.77 KB)