A nandroid backup is an exact copy of everything on the phone when the backup is taken. It should be done in recovery (CWM/TWRP etc) before you flash a ROM/Theme/Kernel etc.
It backs up the boot, system, data and cache partitions so that if whatever you're flashing fails, you can boot back in to recovery and restore your back up.
If you're using Titanium and deleting/freezing system apps, it's also a pretty good idea to have a nandroid backup to restore with, in case you delete and app that the phone needs to function correctly (launcher, dialer etc).
It's essentially a safety net so that if you break something, you can fix it easily.
