Hi! mitcho , I had already add a bluetooth modem to Arduino last month , and it works very well , you can see the pic :
I don't know your bluetooth modem works at 3.3v or 5v , my modem is work at 3.3v ,so I need to turn 5v to 3.3 . the leaved things is just connect the pin0(Rx) of Arduino to the TX of your modem , pin1(Tx) of Arduino to the RX of your modem , than connect the BT to your PC or PDA , you can get the date from Arduino and can send date to it just like there is a series cable , and you can use Arduino IDE to download program to the board via BT modem .