I was recently given an iPhone 3G which was network locked to a major carrier. The owner was looking for a way to get the phone (which was well outside of its justifiable period of lock-in) to work with another network. The process is fairly straightforward but the instructions are scattered across a number of forums and blog posts. The network lock is provided by the baseband, which on most iPhone 3G/S is 05.15.04 (with an iOS version of 4.2.1 which was the last one released by Apple).
The best baseband for unlocking is 05.13.04 but you cannot simply downgrade – you need to upgrade to the iPad baseband 06.15.00 and from there you can downgrade. The tool for this is Redsn0w version 9.14b1 (get it via your favourite search engine). The process is: download the iPhone firmware (more than likely 4.2.1), connect your iPhone to your pc and run Redsn0w. Click ‘Extras’ ->> ‘Select IPSW’ ->> from the tick menu select ‘Install iPad baseband’. Once it has completed, run Redsn0w again and select ‘Downgrade from iPad baseband’ and ‘Install Cydia’.
Verify you are on the correct baseband by going to ‘Settings’ ->> ‘General’ ->> ‘About’ and look for ‘Modem Firmware’.
Once you are on 05.13.04, open Cydia and install the latest version of Ultrasn0w. Run Ultrasn0w and insert your SIM of choice. If you have trouble getting a signal or the phone is unstable, take a look over here.