You'd be better off asking this question in an Android forum
Getting Android to talk to Arduino over bluetooth is pretty straightforward but how to program your Android, thats a whole other game
I believe you need to get very specific about the Android device as well. One reason for buying my ICS tablet was to team up with an Arduino. It has no trouble seeing the Arduino bluetooth but I have tried every freebie bluetooth app in the shop, all to a lot of despair and no avail, and now do what I should have done in the first place - use a Dell XP laptop.