In their latest blog posting, the Dev-Team assures us that version 0.9 of Ultrasn0w is working better than ever to unlock your iPhone 3G/3GS. Still, there are a handful of issues remaining (such as unusual battery depletions, T-Mobile idiosyncracies, etc.), and the Dev's offer a bunch of tips to handle each.
Just to remind everyone: it is now OKAY to upgrade to OS 3.0.1. The upgrade doesn't update the baseband, so both Ultrasn0w (via Cydia) and Redsn0w (for 2G phones) work. However, upgrading to 3.0.1 through iTunes will nuke all your jailbroken apps, so proceed accordingly.
If you're still not sure how to proceed, be sure to follow our guide to jailbreaking your iPhone.