Great tips and steps pulled from a post by neko:

Jailbreaking iPhone 3G with OS3.1:

1. Download PwnageTool 3.1

2. Download the unhacked OS3.1 firmware from Apple. https://appldnld.apple.com.edgesuite.net/content.info.apple.com/iPhone/061-6600.20090909.AwndZ/iPhone1, 2_3.1_7C144_Restore.ipsw

3. Run PwnageTool and select the unhacked firmware from step #2. Modifying the firmware should take about 4-6 minutes.

4. A modified version of the firmware should appear on your desktop.

5. Insert an AT&T simcard into the iPhone.

6. Put your iPhone in DFU / hard reboot mode. (Power + Home button ritual)

7. Plug in your iPhone to your computer via USB.

8. Start up iTunes.

9. iTunes should detect the iPhone as in recovery mode and should give you a button to restore.

10. On a Mac, hold down the Option key and while clicking on the “Restore” button in iTunes to choose the location and file to use.

11. Select the modified firmware on the desktop (created from step #3)

12. Restore.

13. Allow anywhere between 10 – 15 minutes for the restoring process to complete.

14. The iPhone should reboot itself. Allow 3-5 more minutes for the phone to configure the new settings.

15. Cydia should appear. Install repo666.ultrasn0w.com into Cyndia’s sources.

16. Install and run “Fuzzyband” from Cydia to downgrade your iPhone’s BaseBand / radio firmware to version 04.26.08.

17. Remove the AT&T and insert in your non-AT&T sim card.

18. Reboot your iPhone.

19. The phone should be able to use non-AT&T network now (T-Mobile, Verizon, etc).

20. Enter in any appropriate network settings (E.g. for T-Mobile: Settings –> Carrier –> General –> Network –> Cellular Data Network –> Cellular Data section APN: internet2.voicestream.com)

21. Your phone should now work with your carrier.

22. This firmware hack will not brand your carrier on the top corner of your phone. You can install “MakeitMine” from Cydia to customize the top of section of your phone. This step is not required. It’s only for cosmetics.