You need to use Redsn0w to create a custom firmware which does not have a baseband. Then put the phone into pwned DFU mode with Redsn0w and option restore to the custom ipsw. Then Jailbreak the phone pointing redsnow to original apple IPSW and chose instal Cydia. I had to do this stage twice on mine for some reason since Cydia did not instal the first time.
Then install ultrasn0w to unlock.
There is a good tutorial here....
http://www.iclarified.com/entry/index.php?enid=17344
Note the jailbreak will be tethered unless you have the old bootrom 3GS.