Blacksn0w, child of overserious shadow-lurker GeoHot and brother of equally straighforward jailbreak app Blackra1n, is now available, and should make unlocking your late-version iPhone 3G or 3GS a dead-simple process. Before you dive in, though, there's one caveat:
Apple can permanently patch the blacksn0w exploit in their next firmware update. You must download Cydia's "On File" system in case Apple blocks more exploits in future updates.
It's still safe to run the tool, but keep in mind that Apple can—and probably will—patch the core exploit used by Blacksn0w, rendering your unlock useless, or worse. Running On File will ensure you can downgrade in the future, so you don't lose whatever precarious carrier/plan/phone arrangement you've so fallen in love with.