These are the steps I took to secure my Linux box.
First off I am behind a Linksys router with builtin firewall. Checking it at grc.com it shows up as Stealthed.
1) Install and run Bastille.
2) Shut off any services you do not need.
3) Installed Guidedog, make sure no unneeded services are allowed.
4) Ran Nessus to check for open ports.
5) Installed integrity checking apps samhain and tripwire.
6) Not sure what app it is now but mdssums are checked weekly.debsums I think.
If you are running Debian read:
Securing Debian Manual