With the back-to-back new of (a) the Library of Congress giving jailbreaking the green light, (b) the debut of the web-based JailbreakMe, and (c) the latest release of ultrasn0w, there's virtually no reason why you can't (or shouldn't) unlock your iPhone 3G/3Gs running the latest iOS 4.0.1. Here's how:
1) Jailbreak your iPhone, using JailbreakMe. Here's our handy-dandy tutorial.
2) Run the latest version of ultrasn0w to unlock your phone. Yeah, there's a tutorial for that, too.
iPhone 4 owners will have to wait a little bit longer for the unlock, which Dev-Team is promising by Wednesday.