Just download SP3 directly. You don't install Windows 2000 Service pack 1,2 and 3 before installing Service Pack 4, and Backup exec is no different.
There's one hotfix following SP3 worth applying too.
What did you try installing? The first link Ken posted on that page was the full install for 9.1 rev 4691.1. Rather than being "Service pack 1" it actually refers to Hotfix 1, which adds the desktop and latop option.
If you have already installed the product, just go here (as stated by ken):
http://seer.support.veritas.com/docs/278302.htm
Download and install SP3.