I'm not sure what happened... I think I accidentally told iTunes to sync Apps - but my iPAd is still Jailbroken (I can run apps that were installed, and Backgrounder still works) BUT Cydia, Installuous and the other special apps got removed on me.

How do I get them back? Do I have to do a full restore and then reinstall all the apps?

try going to your search page and search for the apps like cydia.
If they show up they are still installed, but you just have them hidden.

If they dont show up you will have to find them online and manually install them.
If that seems to complicated for you, yes a restore and rejailbreak will work too.

And by the way, you know installuous is illegal right?