@bhutanesedude.
You may want to check whether your handset is set to be visible to other devices. In most phones that I know of, this is set to OFF by default (ie, your phone isset to beinvisible to other devices in its vicinity). You can check this by going to Bluetooth Settings>Visibility.
Also, check the manual for the 4-5 digit PIN that the headset comes with. You will need this to pair the phone with the headset.