Assuming it is currently on iOS 3.1.3, you will need to 'hackivate it by downgrading it to 3.1.2 then by running blackra1n.
First you need to download the iOS 3.1.2 package, which can be downloaded at this link:
http://www.felixbruns.de/iPod/firmware/
To downgrade put your phone into DFU mode and restore it manually by selecting the iOS 3.1.2 package (ctr + shift and clicking restore).
1) Once you have reverted back to iOS 3.1.2, your phone will display the message "The SIM card inserted in this iPhone does appear to be supported" (No need to worry, the following steps will solve this).
2) You will then need to jailbreak and hackivate your iPhone by running Geohot's blackra1n program. This can be downloaded here:
http://blackra1n.com/
3) Once downloaded, save it to your desktop as you will need it for the jailbreak.
4) Plug your iPhone into your computer and ensure that iTunes detects it, then run Geohot's blackra1n program and click "Make it Rain".
5) Let the program run and do not unplug your device once it is working.
6) Your iPhone would then reach a screen with that asks you to "Please select packages". Select the Cydia and sn0w.
7) Once you have selected the packages tap install and wait for your iPhone to load and reboot.
9) Once it reboots you would have successfully downgraded, jailbroken, hackivated and unlocked your iPhone on iOS 3.1.2.
Hope that helps, please feel free to post any further questions. I'm happy to help.
