Opa... veja que programar para bluetooth não é algo assim tão bacana... o problema é o satck em que cada fabricante faz uma coisa e outro não... e isso impossibilita algumas compatibilidades...
Tive a curiosidade de fazer algo assim e por falta de grana não pude comprar um módulo bluetooth http://www.sparkfun.com/products/10938 e existem datasheets e assim vai... nesse a comunicação é SPI então no próprio arduino é só procurar exemplos com SPI e assim vai...
Para resoler o impasse do custo... meu note book tem bluetooth integrado e fiz com que ele servisse de bluetooth pro meu arduino.. e ficou assim ( notebook rodando java + bluecouve e serviço serial para se comunicar com o arduino) + celular android com um simples aplicativo para trocar informações entre o celular e o arduino.