In addition to the test suggested by Ignacio Vazquez-Abrams you might also want to create separate checksum files for your tarballs. While it doesn't catch tarballs which got corrupted during their initial creation, it will allow you to later verify that the files are still in their original state, and that they haven't gotten corrupted by disk or file system problems.
Assuming the backup backup_20110724.tar.gz is created, you might also want to have something along the following command being run:
sha256sum backup_20110724.tar.gz > backup_20110724.tar.gz.sha256
It will then create a file containing something like this:
You can then later verify the integrity doing something along these lines:
sha256sum -c backup_20110724.tar.gz.sha256