[T-Mobile Samsung Galaxy S 4] Skipjacks:
Yes. It's completely possible. And easy. Let's clarify what a few thigns mean first...

"Rooting" means giving you access to the system partition of the phone storage. That means the files that run the phone itself as opposed to just your personal data. This is done with an app called Superuser that kind of acts as a gate keeper between the system partition adn the rest of the storage. The only thing that 'rooting' does is install the Superuser app as a system app just like all the apps that came on the phone when you bought it like the phone app and the messenger app, etc (Instead of as a user app like everything you download from the Play store). That's it. Nothing else.

Once that Superuser app is installed it allows or denies permission for other apps to access the system partition of the device. (It prompts you each time an app wants to access the system partition and asks you if you want to lef t it)

If you root the phone using CF Auto Root, again you are only installing the Superuser app. Nothing else. But once the Superuser app is installed you can then use an app like ROM Manager to install a recovery. You will tell ROM Manager to install a recovery and you will get a pop up promot from Superuser saying "Do you really want to let ROM Manager have root access?" You say yes, and it will install the custom recovery.

Recovery is sort of like a mini operating system you can boot into instead of the phone. From inside recovery you always have full root access. You can do anything. Install anything, wipe anything, etc. So once recovery is installed you can then wipe the phone clean and install CyanogenMod.

Doing this will wipe out the Superuser app you installed with CF Auto Root because you will wipe the system partition clean. But it will install a new set of system files in the same sopt and a new copy of Superuser will be included. (Actually on CM10 Superuser is integrated into the ROM framework, but same thing...) So when you boot into CyanogenMod for the first time you will already be rooted and have Superuser. (Well, you'll have the ability to get Superuser. On CM you have check a box in settings to give you root access, but it's as easy as that. No fancy stuff. It's disabled by default.)

What the CyanogenMod team is saying is that since you need Odin or Heimdal to install Superuser using CF Auto Root just so you can use ROM Manager to then flash a recovery, you may as well just use Odin or Heimdal to install a recovery. Then boot right into recovery and flash CyanogenMod.

The short version of all this is that if you ant to go right from bone unrooted stock to CyanogenMod, rooting it first is just an extra step. It won't hurt, but it doesn't help either. Just adds extra steps and time to the process. But there's a downside to doing that, which ties in nicely with your next question....

A Nandroid is a full backup of everything. It's like you're own little custom flashable ROM. The data from it isn't really usable unless you flash the entire thing to restore the phone to the same exact state it was in when you made the nandroid.

In other words, while a nandroid will back up all your user and app data, it's not putting it into a usable form for restoring after installing a new ROM. There are apps that let you extract data from a nandroid but it's a pain in the butt.

By rooting the phone first using CF Auto Root and installing Titanium Backup on the stock ROM, you can back up all your apps and user data. Then wipe the phone clean, install CyanogenMod, then install Titanium again and boom...your saved app data will show up in Titanium ready to be restored!

Read up on how to change the storage location in Titanium form EXT SD Card ot Legacy after installing CyanogenMod though or you'll get errors in Titanium. It's super easy. It's just a setting in Titanium. But you have to do it because it's set wrong by default.

No. Yes. Kind of.

A nandroid backup is a saved version of your entire phone. Ssyem data, user data, settings, text messages, contacts, apps, etc....it's like a 'system restore point' if you'd care to use Windows XP jargon.

ClockworkMod is the thing that lets you make a Nandroid backup. You will also see discussion of TWRP Recovery and PhilzTouch. Same thing.