I highly suggest MyBackup Pro.
Backs up all of your apps, ALL of your data (you select what exactly you want it to backup, and my "all data" I mean; texts, call logs, settings, homescreens, EVERYTHING).
I have yet to restore everything, but I read that it also backs up your in-app settings and everything. But don't take my word for this.
If you don't want to spend the $5, there is a free version that will last for 30 days.
I use to not back anything up, and would use AppBrain to save my apps - but the process of still having to install each individual app, was a pain. MyBackup Pro saves all your apps [zipped] on your SD card, so when you restore - that's it. You don't have to "tap" through each app, approving\installing it. They're just there.