Factory unlocked phones are way too expensive. As for the 3GS, the jailbreak (and hence unlock) is tethered, which means you'll loose unlock after you reboot your device. This is not true for older 3GS models. But now you'll only get 3GS with new bootrom, hence the limitation.
You'll have to connect to computer and re-jailbreak every time you reboot iPhone 3GS. That takes 30 secs-1 minunte. But is still very annoying.
Also, if you can live up with this, make sure the iPhone you are buying is at 3.1.2 firmware, not at the latest 3.1.3, which cannot be unlocked.
The scenario will change in future, when new unlocking tools are released.
Sheesh..sorry for the long post but I think its necessary for you to know these thing if you are going for iPhone 3GS
P.S Oh yes, the same is not true for iPhone 3G (no loosing unlock after reboot), but still you need it to be at 3.1.2 to be unlockable.