First things first. Go to Settings - General - About and check the Modem Firmware. If it's
not one of these - 4.26.08, 05.11.07, 05.12.01, 05.13.04, then follow
this tutorial. If the Modem Firmware
was one of the mentioned above, follow
the same tutorial without installing the iPad baseband.
After you jailbreak the phone, fire up the Cydia app, let it update and install ultrasn0w. This will make you reboot the phone once more. Once this is done, you should have an unlocked iPhone.
Notes: while downloading the jailbreak tool, make sure you find the right beta version. There are newer versions, but they jailbreak newer iOS versions.