3.1.2 users must use blackra1n’s blacksn0w option to unlock. See the black ra1n guide here. Alternatively, if you are already jailbroken you can add the unlock by adding blackra1n.com as a repository and installing blacksn0w from Cydia.

3.0 Users can use ultrasn0w listed below:

Dev team has released Ultrasn0w, the iPhone 3g unlock. Here are the instructions and info from the dev team site.

Note, you must jailbreak your iPhone first. This is only for iPhone 3.0.

Ultrasn0w for iPhone 3G is ready!

1. Ensure you have upgraded to iPhone OS 3.0
2. Jailbreak your iPhone 3G using redsn0w or PwnageTool (this will also install Cydia/Icy)
3. Run Cydia or Icy
4. Please add the repo repo666.ultrasn0w.com to Cydia or icy
5. Search for ‘ultrasn0w’ in cydia or icy and install ultrasn0w
6. Reboot your iPhone 3G
7. T-Mobile USA users should disable 3G before using ultrasn0w
8. Enjoy

No, this will not currently unlock 3gs ad that cannot be jailbroken yet.