Agreed. Unlocking is the money-maker. Most people assume they can do the jailbreak themselves.
To answer your question, though, your iTunes may still have the 3.1.3 firmware on the hard drive. If you do ALT-restore in iTunes for Mac, or CTRL-restore for Windows, it will let you select what file to use for the firmware. If it's not there, do a google search and you can download it. Make sure you download the 3GS version specifically.