IMPORTANT*: Unfortunately if your serial number begins with MC you won't be able to jailbreak on 3.1.3 but you can jailbreak on 3.1.2.
Create a folder on your desktop called Pwnage
Download RedSn0w from here and place it in the Pwnage folder. Likewise, download the latest 3.1.2 and 3.1.3 firmware and place it in the same folder.
NOTE*: The iPod touch 3.x firmware must be purchased from iTunes. iTunes will save the firmware files here:
C:Documents and Settings USER NAME Application DataApple ComputeriTunesiPod Software UpdatesiPod2,1_3.1.2_7D11_Restore.ipsw
C:Documents and Settings USER NAME Application DataApple ComputeriTunesiPod Software UpdatesiPod2,1_3.1.3_7E18_Restore.ipsw
(You must enable 'view hidden files and folders')
If you can't find the files, you can search Google for the IPSW.
Extract the redsn0w application from the RedSn0w zip file to the Pwnage folder.
Connect your iPod Touch to the computer and launch iTunes.
Select your iPod Touch from the list of devices on the left. Now hold down Shift and click the Restore button. Restore is preferred as it won't create any wasted space on your iPod Touch.
Navigate to the Pwnage folder on your desktop and select the 3.1.3 firmware ipsw if your serial number does not begin with MC. If it does begin with MC then select the 3.1.2 firmware. Click the Open button to continue.
Once iTunes has finished updating your iPod Touch to the desired firmware you may launch redsn0w.exe from the Pwnage folder on your desktop.
Once RedSn0w opens click the Browse button
Select the 3.1.2 firmware ipsw we placed in the Pwnage folder on our desktop then click Open
You will be asked if your serial number begins with MC. If it does then click the Yes button; otherwise, click No.
Once the firmware has been verified click the Next button to continue.
Make sure Cydia is selected.
If your serial number begins with MC you will only see a Cydia and a Boot Tethered Option. Otherwise you have the ability to add a custom boot logo or restore logo. Click to select the option which will open a file dialog. Select the logo you would like to use and click the Open button.
Click the Next button to continue.
RedSn0w will now prompt you to put your device into recovery mode. Press both the Power and Home buttons continuously until the help message disappears.
RedSn0w will now upload the exploit to your iPod touch.
Once this is complete you will be notified that RedSn0w is done. Click the Finish button.
When your iPod Touch finishes rebooting (5 minutes or so), it will be jailbroken with Cydia on the SpringBoard.
***NOTE: Remember to reboot a tethered iPod touch follow Steps Three through Six then select "Just boot tethered right now" in next step.