The 2G did not see that much action in the jailbreaking community at the time. The 3G was where jailbreaking first sparked really.
Fresh restores can be done by clicking on the restore button in iTunes. Make sure you backup your device prior to doing so.
When you're on a fresh copy of iOS 3.1.3, open up Safari on your phone directly, enter jailbreakme.com, and slide the slider. The jailbreaking portion is by far the easiest since it's just a simple slide and finish