At a minimum you should backup the Backup Exec Installation directory and all subdirectories daily, after all other backups have completed. This will capture the databse file, logs, and catalog directory (check Tools -> Options-> Catalog to verify your catalog location is not somewhere else other than the default location).
I would also recommend using a dedicated easy to identify tape for this purpose. Many sites will use Slot 1 of their tape library, or partition a special slot for this purpose. If you're not using a tape library than use a specially marked tape. In the event of a disaster, you'll want to find this tape first to restore the catalog information before restoring all the other data.
I would also recommend creating a CloneCD, by going through the Installation GUI again, and selecting that option. This will create an unattended installation CD which is nice, if you don't have the license keys handy (in the event of an emergency reinstall).
The restore process is fairly painless-
Load a new server
load BE10
Catalog the backup server backup tape.
Restore the Veritas directory and subdirectories (use overwrite existing files method).
Reboot
Use BEUtility to reload database from backup.
All jobs, logs, media and restore selections will be restored.
Of course this should be practiced from time to time to refine your individual processes.
