Here's a quick demo of an Android application from BlueAnt that pairs up with their Q1 Bluetooth headset. They expect to support it with other headsets in the future.