In itunes shift/option click restore to the 3.1.3 firmware (a window will pop up when you do this where you can choose your firmware). Do not update to 4.1 as there is no unlock for that.
Once at 3.1.3 use redsnow 0.9.4 to jailbreak and activate it (unless you still have a ATT sim then you can use that to activate it). You will need to point it to the 3.1.2 firmware.
Once jailbroken open cydia and install ultrasn0w then reboot. Your phone will now be unlocked.
Successfully downloaded 3.1.3 and 3.1.2, thanks for the link.
I option/restored to 3.1.3.
Downloaded 0.9.4 and opened it.
Now it says to select current ipsw.
I chose 3.1.2.
Now it offers 6 choices, including "install Cydia", "unlock", and "already pwned".
If I choose these three it then asks me to Google for the binary code for 3.9 and 4.6.
Think I'm going off the rails here; I have a 3G not a 2G.
What is my next step?
If you are getting those options then you selected the wrong .ipsw, those are the options for a 2G. a 3G .ipsw should start iPhone,1,2 a 2G will start iPhone 1,1
4.0.1/4.0.2, sure - but I've seen vids on YouTube that show 4.1 on a 3G isn't very different to 3.1.3. Seemed like it to me after I'd gotten it up to 4.1, as well.