An overview of the steps required to secure a unix machine
Read your vendors announcements on security issues, read lists like bugtraq. Apply the patches when they are announced!
you should use netstat -ap and remove any services you are not using, preferably remove them from the machine entirely, but at least prevent them from running. Of any services that you must run, make sure they are firewalled as much as possible, and that tcpwrappers(5)? are used to protect against them. If you are really paranoid you should remove them, firewall them, and tcpwrap them. Consider firewalling outgoing connections too, making it difficult for an attacker to install further software.
This reduces the chances of a remote intruder getting into your system.
Remove as many root running programs as possible, either don't run them, or run them as a normal user. Linux has capabilities, use these to allow programs that would normally run as root to run as a normal user with elevated privileges. (eg: ntpd can run as a normal user with the bind low ports privilege, and the set the time privilege).
Use find(1) to get a list of all the suid programs on your system. For each program evaluate if it's necessary to have on your system at all, if not, remove it. If it's necessary, but doesn't need to be run by normal users, then remove it's suid bit, and perhaps it's group and other rwx bits too. if it's required for some users to run (eg: su/sudo) then create a group for the people that can use this command and put this command in that group, and remove the other bits. Do this even if all the users on your machine should have access, an intruder may get access via a remote service (for example http) and get the access of that service.
Mount as much of your filesystem as possible readonly, eg: /, /usr, /etc should be mounted readonly. /var,/home,/tmp should be mounted readwrite and noexec. partitions users can write to (eg /home and /tmp) should be seperate to partitions users can't directly write to (eg: /var). /var/tmp should be a symlink to /tmp
Set a boot password and a bios password so someone at the console cannot circumvent security that is in place. Consider physically securing the hardware (zcat also suggests change ctrl-alt-del in inittab so it doesn't reboot the box when the keyboard 'gets dropped', also disconnect the reset and power switch buttons and install an internal PSU/UPS. If you're concerned about espionage, consider using a cryptographic filesystem.)
Set programs/critical system files immutable via chattr(1), run tripwire.