I was going to title this “Unlocking the iPhone 3GS 3.1.3″ and then I realised that there are a billion posts out there like that, and there doesn’t seem to be a one-size-fits-all answer to this. So, here’s what worked on mine.

1. Grab a copy of Spirit (has Mac and Win versions)

2. Make sure you have already activated your iPhone (i.e. turned it on and synched to iTunes and you are able to register with the cellphone network)

3. Connect the iPhone and run Spirit, hit Jailbreak

4. Install Ulstrasn0w and you have unlocked the iPhone

NOTE: I’ve discovered and confirmed Ultrasn0w doesn’t work with baseband 05.12.01 yet.

The difficulty for me with the 3GS was that the older methods of unlocking it didn’t work for me, because I have a native 3.1.3 model…which has intermittent success depending on the actual model number. Spirit worked though.