iPhone DevTeam's 3G and 3GS software unlock, now with added PwnApple. Compatible with basebands 04.26.08, 05.11.07, 05.12.01 and 05.13.04! Thanks to @sherif_hashim and @Oranav for contributing baseband crashes.
You can find instructions on how to install the UltraSn0w unlock here
Note: The iPhone Dev-Team has not yet released the jailbreak utilities for iOS 4. So those who want to update should wait a little bit. Those on 3.1.3 with the 05.12.01 baseband can install UltraSn0w right now to obtain an unlock.
We will also be updating our jailbreak and unlock wizards shortly.