That didn't take long.
Pwnage Tool 3.0 (torrent) has been released and allows you to jailbreak iPhones running OS 3.0. There are some caveats, however.
The first is that it won't work on the new iPhone 3GS -- which is a bummer for everyone that just purchased Apple's new handset. No word on when/if it will be JB'd, but I wouldn't bet against it.
Also, if your iPhone is already jailbroken and unlocked, don't upgrade to 3.0 or you can lose your unlock. You'll have to wait for ultrasn0w to do that.