Recovery-cmw-hercules.tar (doesn't have to be the latest, you can update it later). This can be found in other recovery threads, as the process remains the same.
Odin3 v1.85 (or any other compatible version)
root.zip found Here
1) Make sure Kies is exited, and you have the drivers installed for Odin. If not, check the other threads as this has been covered many times
2) Just select your CWM recovery for PDA once you are in DL mode (which is achieved by holding down VOL Up and VOL Down when the phone is off as you plug in the cable). Select vol up to confirm dl mode.
3) In Odin, leave the default boxes (Auto reboot and F. Reset time), and then select PDA and choose the .tar file we found earlier. Make sure odin sees your phone properly and start this!
4) once you have CWM recovery installed copy the root.zip to your sd card, and boot into CWM recovery. Do a Nand Backup and then install root.zip and enjoy!
5) Delete that crappy bloat!
For those having connection issues in Odin, try the following.
1) Exit Kies
2) Change to a different USB port
3) Reinstall your USB drivers.
I kept getting an error, and the above fixed that.