Finally Dev team released Redsn0w 0.8 with support of Winterboard and Ultrasn0w also. Redsn0w is a easy to use, multi-platform, multi-device jailbreaking and unlocking tool for the iPhone 2G (original iPhone), the iPhone 3G/3GS and also the iPod touch(1st generation and second generation). Currently it is available for Windows, Mac OS X and Linux. After jailbreaking follow this guide to Unlock Your iPhone 3GS OS 3.0 With UltraSn0w. Ultrasn0w is also updated to 0.8 to unlock iPhone 3GS. After unlocking with Ultrasn0w on 3GS reset your network setting once from Settings->General->Reset->Reset Network settings once.
Download:1. Ensure you have upgraded to iPhone OS 3.0 (Do not upgrade to 3.1 yet if you want this unlock!)
2. Jailbreak your iPhone 3G using redsn0w (this will also install Cydia/Icy)
3. Run Cydia or Icy
4. Please add the repo repo666.ultrasn0w.com to Cydia or Icy. That last “o” is actually the number zero “0”! If you use the letter “o” you’ll get an error.
5. Search for ‘ultrasn0w’ in cydia or icy and install ultrasn0w
6. Reboot your iPhone 3GS
7. T-Mobile USA users should disable 3G before using ultrasn0w