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 . If the Modem Firmware was one of the mentioned above, follow 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.