First download the following.
1. iOS firmwares -Chose the firmware you want and the exact phone model you are using.
http://www.ijailbreak.com/iphone/where-to-download-iphone-firmware-restore-links/
2.Sn0wbreeze - Select the software version that matches your firmware version selected above.
http://www.ijailbreak.com/ijailbreak-downloads-section/
3. itunes 10.1 or higher.
Steps to restore iOS.
1. First go to C:\widows\system32\drivers\etc.
2. You will find a file named "hosts". Open it with notepad and add "74.208.10.249 gs.apple.com" at the bottom.
3. Now click save. It will say that you can't overight the document. So save the document to somewhere else. Now delete the extension of the file and copy it to the C:\widows\system32\drivers\etc. It will overight the existing "hosts" file.
4. Open sn0wbreeze. (If it gives an error, download java form here -
www.java.com)
5. After you open it, Simply follow the instructions (At some point they'll ask to select a mode, you have to select "Simple Mode)" and select the ispw you downloaded earlier(It takes some time. So be patient) This will create a custom iOS. It will be saved to the desktop.
6. Open itunes. Connect the phone and put it on DFU mode.(Sn0wbreeze will guide on how to put your phone on DFU) When your phone is in DFU mode, screen will be black but still PC recognizes the phone. If the phone shows itunes and data cable, then it is not on DFU mode. So make sure that your phone is in DFU mode.
7. After PC recognizes the phone it will pop up a message saying that your phone is in recovery mode. Now select the option "restore" on your itunes while pressing left shift button.
8. A new window will open. Select the customized ispw (The one that sn0wbreeze made, Not you one you downloaded).
9. After selecting the ispw, the new iOS will be installed. When it completes phone will restart and it will be already jailbroken.
10. If your phone is not a factory unlocked, remove your sim, launch cydia, then manage>souces>edit>add. Then type the following:
http://repo666.ultrasn0w.com. After adding the source you have to install it.
11. After install completes, phone will be rebooted.
12. Insert the SIM. Put it on airplane mode. Again put it on normal mode. You should be able see your network provider's name and signal bars. Your phone is UNLOCKED.
Important: My advice is to you that you should not update your phone to iOS 5 or 5.0.1. for two reasons.
1. Unteathered Jailbreak is not available for iOS 5. So if you jailbreak your phone now it has be connected to a PC everytime when you switch on the phone.
2. There are some bugs in iOS 5 that drains your battery very fast.
Hope this would help. If you face any problem while doing it, you can PM me. I will help.
Cheers!