What sort of data are you anticipating sending? And how important is battery life / power consumption? And do you ever anticipate needing to send to an iOS device?
If you think you might want to have an iOS device in the mix later, then you need to use BLE.
If it's only ever going to be Android, you can use 'classic' Bluetooth with a cheap module like the HC05, but that does consume more battery. On the other hand, classic Bluetooth modules support a 'serial port profile' which means that once the connection is made, you can just pass data to and fro as if it's a cable.
With BLE different modules can behave very differently; you'll probably need to choose a module that support a 'Transparent UART' service, which achieves the same (though the coding is different) as the serial port profile on a traditional device. There is no defined BLE standard for this - they'd rather you use one of the profile like 'heart rate monitor' and so on - so all the chips tend to work differently. For example, some will output a 'Connected' message when the phone links to them; others will be completely transparent. Some will need a load of commands sent from the Arduino to set the correct options before a connection, others will need more work.
I played with a few different BLE modules over the summer. The MicroChip RN4020 was a nightmare; I could only get serial data transmission to work in one direction - but weirdly, that varied depending on the platform. I could send from Android to the 4020, but not receive, and the reverse was true when using an iOS app.
The BlueCreations BC118 with MelodySmart was pretty easy to code for - but it did need some setup commands sending to it, and as far as I recall it outputs a status string when a connection happens (which may or may not be an issue, depending on how much control you have over the Arduino code).
The MicroChip BM70 worked fine with both iOS and Android, and can be set up to be pretty much 100% transparent. The only downside was that configuring the module needs a Windows tool to flash a parameter table; if you want to be able to control parameters from your device (like the Arduino) then you pretty much have to forget the auto transparent mode and drive the whole thing yourself.
There are probably different BLE modules with other quirks too.