Hi!!! I'm making a proyect which envolves bluetooth communication between a phone with Android and a little robot with Arduino. I want to send commands to the robot from the phone and I wanna recieve some status information like temperature, battery remaining charge and the robot will be integrated with a webcam... so I wanna send this images from the webcam to the phone. Is it possible???? Or I'm just like crazy and need another microcontroller (by the way I'm using the Atmega328p-pu that comes with the duemilanove) or another way to communicate them to handle all this "channels" of information. Could I multiplex it or decode it??????
Here you go:
http://iteadstudio.com/application-note/make-arduino-talk-with-android-by-bluetooth/
Itead has made an example how one could do this.
Here's a good tutorial for the Blue SMiRF found at Sparkfun
http://www.arduino.cc/playground/Learning/Tutorial01
this tutorial is for a computer, but in theory (and with a little configuration 
)it should work for your android phone.