If I'm running OK, I backup once a week and delete the old one of the same ROM/Theme.
But yes, I'd backup before installing a new ROM or Theme, then if that ROM or Theme is working good after a day or say, I'll back it up too. Keep in mind, Backups eat up a good amount of SD card space if left on the phone and not moved to a PC.
See here for naming conventions to help you remember what each backup consisted of.
Re-Naming Nandroids?