Most Bluetooth headsets are compatible with BlackBerrys. Personally, I've used Motorola headsets for years, as I have found them to be very reliable. Other brands have also gotten favorable feedback here.

It comes down to personal preference. Never hurts to solicit feedback from the people you know, or visit a retail store and ask questions.