Besides Redsn0w and Pwnage Tool, iPhone dev team also updated Ultrasn0w unlock, the tool to unlock iPhone is now fully compatible with iOS 5.1.1. iPhone Dev Team’s iPhone 4, 3G, and 3GS software unlock, now with added PwnApple. Compatible with iPhone 4 baseband 01.59.00 and iPhone 3G/3GS basebands 04.26.08, 05.11.07, 05.12.01, 05.13.04, and 06.15.00! Thanks to @sherif_hashim and @Oranav for contributing baseband crashes.
You can download Ultrasn0w in Cydia , you need to have done the jailbreak on your device and a baseband of the aforementioned. If you have one of these basebands then you are good to go, or you can hardware unlock your iPhone i.e. Gevey Ultra Unlock.