Pair an Apple Bluetooth Headset

I used this to pair my headset with my iMac, and make calls using Skype.

Set the headset to be discoverable

Turn off the headset.
Press and hold the headset button for about eight seconds, until you hear the startup tone and then five quick high beeps.
The headset is now discoverable and will remain so for about five minutes. The status light blinks while the headset is discoverable.

Turn on Bluetooth on the other device and search for devices

On the device, turn Bluetooth on and set the device to search for other Bluetooth devices.
On the device, choose iPhone Bluetooth Headset and enter the PIN code 0000.