It is necessary to put the headset in to the "pairing" mode. I have a BT530 Jabra and there you just hold the main button down until the light turns Blue (normally red). Once the light turns blue (a convention with all Bluetooth devices), go to the Bluetooth page on your phone.
Go to Options / Bluetooth. Hit the Menu key and select Add Device. The phone will go into a search mode. The headset should be next to the phone when you do this. Both the Labra manual and the Storm manuals have a detailed discussion of this process. 73