This is the process I used to upgrade an iPhone 3Gs running IOS 4.1 baseband 06.15.00 to IOS 5.0.1 while preserving the baseband and the carrier unlock.

Software installed/downloaded:

OS: MacOS Lion 10.7.2
iTunes: 10.5.2
redsn0w_mac_0.9.10b1.zip
iPhone2,1_5.0.1_9A405_Restore.ipsw

I plugged the phone into my computer and backed up from iTunes by right mouse clicking on the phone and selecting “Backup”.

I downloaded the redsn0w application and the IOS install into a folder called JB.

I unzipped the redsn0w_mac_0.9.10b1.zip and executed redsn0w.app from the redsn0w_mac_0.9.10b1 folder.

Clicked Extras.

Clicked Custom IPSW and browsed to the JB folder where I downloaded the iPhone2,1_5.0.1_9A405_Restore.ipsw from Apple.

Since I had an original 3Gs, I selected “No” on the “Will this custom IPSW be used on a newer (fixed) version of the iPhone3GS?”.

This created a custom NO_BB_OLDROM_iPhone2,1_5.0.1_9A405_Restore.ipsw file that will not attempt to update the baseband when IOS 5.0.1 is restored.

Once created, I needed to put the phone in DFU mode. For some reason, I had trouble using the method I had used before. This is what I did this time:

With device powered on,unlocked and connected via the USB cable with iTunes running:
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.
iTunes came up and displayed that it was in recover mode. I tried restoring my custom IPSW from here but I kept getting a 1600 error. So, once I had in recover mode, I fired up Redsn0w again and went into Extras and clicked on “Pwned DFU”.
This put it in DFU mode quickly.

Then, I was able to hold “alt/option” and click the “Restore” button in iTunes.

This allowed me to browse to the custom IPSW: NO_BB_OLDROM_iPhone2,1_5.0.1_9A405_Restore.ipsw.

This installed IOS 5.0.1 on the phone and preserved the baseband (06.15.00) with the applications and settings restored.

Once up, the phone still needed to be jailbroken and unlocked.

I closed iTunes, and brought up Redsn0w again. I needed to point redsn0w to the unchanged iPhone2,1_5.0.1_9A405_Restore.ipsw file. This time, I chose Jailbreak. The only option that I had selected was “Install Cydia”.

After rebooting and verifying the Cydia icon is installed, I needed to unlock the phone.

I launched Cydia and clicked on Manage and then Sources.

Then, I added the Ultrasn0w repository by clicking “Edit” and “Add”. Then, I added the repository: http://repo666.ultrasn0w.com. Note: this took me quite a few attempts on the 27th, due to server load some where along the line. Eventually, I was able to get the repository added.

Once added, I was able to search for and install Ultrasn0w.

I rebooted and the phone was updated, jailbroken and unlocked.