I got it.
Step 1: 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.
Step 2: 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.