What should I backup before installing a new ROM? What do I need to backup (using Titanium Backup) if I want to have the 'same system' after applying new version of a ROM? 

Is it better to set up everything from scratch or restore my data from the backup?

I have a HTC Desire and I'm upgrading from CM rc2 to CM rc4
Jumping between ROMs in the same development series is usually safe without backing up or wiping the data partition (although the cache and Dalvik cache should always be wiped), unless the installation instructions specifically tell you to wipe the data partition (which seems unlikely in this case; if such a drastic change were needed, it shouldn't be a release candidate any more).  I would nevertheless back everything up just in case, both application backup like Titanium Backup and Nandroid backup from the recovery partition, but then I'm paranoid like that.

Jumping to a different series (say, CM6 to CM7, or CM to aosp) you should always back up everything and wipe everything.