First I need to clear something up, I couldn't recall the name of the 'other' app this morning, and a quick google brought me to BackToDeb. I was mistaken, I haven't tried this one at all.
The 'other' one that I have tried and know is free is called AptBackup. You should be able to do a basic Cydia search and find that one. Apologies.
Saying that, I haven't really used AptBackup too much, and that is because I found out about it after I purchased Pkg Backup.
They both do the same thing pretty much.
I like that Pkg Backup backs up to Dropbox, which is where I have a few other tools backing up to. That's a big plus for me, if you don't want to use Dropbox though you can just have it back up to a Contact in your phone, which ends up being called something like Pkg_Backup..... with a bunch of numbers. So that ultimately gets backed up in your Backup that you do when you plug your phone into iTunes.
Saying that, if I found out about AptBackup before PkgBackup I probably would just use that as it is free.
Of course, the third way is to do it manually by ssh'ing into your iphone, assuming you have OpenSSH installed.
ssh in and you can backup and restore the Cydia files using normal linux commands.
dpkg --get-selections > cydia_backup.txt
All of these should do the trick for you. It's all down to preference really, and if you are willing to pay $6 or $7 for Pkg Backup, rather than AptBackup which is free.