The following was done from MacOS 10.7 Lion.

Because I did not use my iPhone 3Gs for a while, I missed getting my IOS 4.3.3 shsh blob saved, so I was only able to use this procedure for IOS 4.1. I used the following procedure upgrade the baseband to iPad version 06.15.00, since I mistakenly updated the baseband to 05.16.01 previously. With this baseband installed I was able to use Ultrasn0w to unlock the phone.

Software used:
Redsn0w 0.9.6RC16: redsn0w_mac_0.9.6rc16.zip
iTunes 10.2 or later
IOS 4.1: iPhone2,1_4.1_8B117_Restore.ipsw

Unzip Redsn0w and launch redsn0w from the redsn0w_mac_0.9.6rc16 directory.

Browse to the IOS restore distribution, in my case, iPhone2,1_4.1_8B117_Restore.ipsw.

Next you are asked to choose whether your iPhone 3Gs is an older or newer model. I had a
3Gs I bought within the first week of release, so I chose “No.”.

After patching the IOS package, you are prompted to choose your options. Only select “Install Cydia” and “Install iPad baseband.”

Next you are warned, because this pretty much a point of no return installation, so make sure you understand the consequences. I needed to unlock the phone to use on the T-mobile network.

Connect your phone via the USB cable.

Now you need to put the phone in DFU mode. I find the following easier than following the on screen prompts:

With device powered on and unlocked:
Hold the Power and Home buttons.
When the screen goes black, count to 2.
Then, release the Power button, and hold the Home button for 10 – 15 seconds.
You know you are in DFU mode, if the screen stays black.

Once in DFU mode, click through the next prompt. Then, redsn0w will update the baseband and install IOS. Once complete and the phone restarts, go to General/Settings/About and verify that the baseband is updated to 06.15.00. Also, verify that you have the Cydia icon installed.

Install Ultrasn0w 1.2.3 from Cydia by adding the following repository under Manage/Sources:

http://repo666.ultrasnow.com

Once the repository has been added, type in ultrasn0w in the search field and install Ultrasn0w.

Reboot the phone when prompted, and you should be set with an unlocked iPhone 3Gs.

Now for the issues that I have with this installation:

Because I had to install IOS 4.1, I lost MMS capability with this installation. Also, since Find My iPhone was not free until ISO 4.2, I am unable to use the service. I cannot get the device recognized to register it to use the service.

I realize that I could upgrade the IOS to a newer version, but from what I have been able to tell any update would have to be tethered at this point, which would not really be practical for me now.