I suppose the first question is why downgrade the baseband now? Well, I got AT&T to unlock my 06.15.00 baseband 3Gs when it was announced that they would if you phone was no longer under contract. The only reason anybody installed the iPad (06.15.00) baseband was to unlock their phone. Since, it was no longer needed I wanted to be able to update my phone without having to use redsn0w to install a custom ISPW each time.

Software used:
Redsn0w 0.9.14b1.zip

Download redsn0w 0.9.14b1.
Unzip redsn0w.
Download the version of IOS currently running on your device. 5.1 in my case.
Launch redsn0w.
Select Extras.
Click Select ISPW..
Navigate to the downloaded ISPW for your version.
Click Back.
Select Jailbreak.

If already jailbroken, uncheck Install Cydia and select Downgrade from iPad baseband.

Ensure that the phone is connected to your computer, and put it in DFU mode or hit Next and follow the prompts on the next screen. It might take you a few times to get the timing right.

Redsn0w will begin fetching baseband files.

The phone will reboot and you will get a message in redsn0w stating that the rest of the process takes place on your device.

On your phone, you will see several message on your phone relating to disk checks and then the familiar running pineapple on screen. Be patient.

Your phone will reboot with the downgraded baseband.

Now, if you want to go back to a completely stock installation, you will need to restore the most currently supported version of IOS (5.1.1 for the 3Gs), after putting the phone back into DFU mode.