The one you pointed to is outdated - it's for the Eclair version of Android (2.1). http://www.unrevoked.com/recovery/
will be the easiest way to root your phone. For more information, search for tutorials on using unrevoked 3.21. I used regaw_leinad's guide to rooting 2.2 but I don't know if that's still valid with this latest OTA.
If you want 4G, that eliminates CM-6 because it doesn't have 4G. Myn is nice. Lots of people swear by Fresh. I like Burnt Droid and Vaelpak roms. All of these have 4G.
Before doing anything read, read, read and read some more. Before flashing new roms (and you won't stop at just one rom), back up and nand (this is creating a backup image of your phone on the sd card). I use MyBackupPro to back up apps but lots of people use Titanium Backup.
I've read that totally bricking the Evo is hard although I was successful
. What I did was pull the battery during an OTA update - so now you know what NOT to do.