Choose a Bluetooth module that has similar interfaces that are available on the Microcontroller. Example, SPI, USB, or parallel Bus. There are modules available with USB interface. As far as the digital design is concerned, this is the only requirement. From Software point of view select a device that allows you to control the device through OpenAT commands and drivers are easily available. From the Analog point of view, make sure you have separate power planes available for Microcontroller and Bluetooth module. And finally form the RF point of view- EMI shielding and on-board antenna (if applicable) will be the biggest challenge.
Many Bluetooth solutions such as BlueCore offer Bluetooth devices with programmable Microcontrollers. You may want to have a look at it.
Hope this helps.