If your system supports immutable and append-only files, use them. If you don't have them, consider asking your vendor when they will be supported in your version of Unix.
If possible, mount disks read-only if they contain system software. Ideally, use hardware write protection.
Make a checklist listing the size, modification time, and permissions of every program on your system. You may wish to include cryptographic checksums in the lists. Keep copies of this checklist on removable or write-once media and use them to determine if any of your system files or programs have been modified.
Write a daily check script to check for unauthorized changes to files and system directories.
Double-check the protection attributes on system command and datafiles, on their directories, and on all ancestor directories.
Consider making all files on NFS-exported disks owned by user root.
If you have backups of critical directories, you can use comparison checking to detect unauthorized modifications. Be careful to protect your backup copies and comparison programs from potential attackers.
Consider running rdist from a protected system on a regular basis to report changes.
Make an offline list of every SUID and SGID file on your system.
Consider installing something to check message digests of files (e.g., Tripwire or AIDE). Be certain that the program and all its datafiles are stored on read-only media or protected with encryption (or both).
If a system has been compromised, assume that it is thoroughly compromised, and that nothing is trustworthy.