Appbackup will backup ALL your applications, not just Cydia. Install it through Cydia and the first time you launch it select "All" in the bottom left corner, then "backup." Sync your iDevice to iTunes as this will copy over the backup settings to your computer. In the future if you need to restore and rejailbreak your iDevice, install Appbackup after syncing your iDevice and jailbreaking it, then "restore". All your applications and settings will be restored.
Oh right, so I can restore the iPhone as a new one, and still keep my apps and settings?