I had some 3GS iphones and 1 iPhone 4. I have Tmobile ... I had an old non working AT&T sim card (any one will work as long as it was activated at some point - also a prepaid card should work - or bum a friends sim).
Plug in your iPhone to iTunes and do a backup just in case. Then upgrade to 4.0.1 if you aren't already on 4.0.1. Then you will need an AT&T sim in the iPhone to get past the activation screen. It will read trying to activate make take awhile ... blah blah ... just slide to unlock and by pass this.
Connect to a wifi network and go to jailbreakme.com in safari and on the bottom of the screen do the slide to jailbreak. This will jailbreak and add Cydia.
Make sure 3G is turned off in network settings. Open Cydia and go through the interface preference (I choose the user one) upgrade the Cydia essential upgrades and after the Cydia reboot then reopen Cydia and go to search. Search for ultrasn0W and install ... BAM! Unlocked 4.0.1!
And if you have a full size sim and an iPhone 4 its possible to trim your sim but I don't recommend it for everyone to try themselves.