*Before you start, each step will take time and effort. It ain't all easy. But remember that with each shortcut you take, with each task you're not willing to invest time in you essentially weaken the security posture of the box. So, since your box is a server connected to the 'net, you eventually will become a liability for others. Please make sure for others you won't.
Investing time now makes it easier to manage/audit later on.
Some steps:
0. Alert. Notify any users their passwords are presumed taken off the system and they should take immediate action. If anyone uses your box as gateway to other systems, notify network admins to investigate their machines.
1. Rescue. Power off the box. Boot with a bootable CDR like Knoppix, FIRE, PSK or whatever your distro offers you. Now rescue specific things like /home, config files, database dumps. Whatever you rescue, if it's human readable data: read it. Do save a copy of /var/log. Do not save crontabs or binaries. Do invalidate any backups you made unless you have external means of verifying integrity that can't be tampered with. Do not save /etc/shadow for purposes other than forensics. All passwords are invalidated the moment someone gains root account access.
2. Restore. Use the three R's: repartition, reformat, reinstall Linux from scratch. Do not use a backup unless you can verify integrity.
3. Reconfigure and harden. Set up separate partitions and mount them with appropriate flags (/user=ro, /tmp=nosuid,noexec* etc, etc). *may break some apps. In your case: change all passwords. Install only what you need NOW. Harden your kernel with Grsecurity, OpenWall or LIDS. Do not run services you don't need. Don't run vulnerable services. Do run services under lesser-privileged accounts. Do guard IP-level access to critical services by built-in mechanisms (like OpenSSH and Xinetd have), TCP wrappers and the firewal (and and not or or). Install and configure a filesystem integrity checker like Aide, Samhain or tripwire. Save a copy of the binary and initial databases on read-only media. Install an IDS like Snort or Prelude and watch those logs. Install a tight firewall and only allow access to necessary ports. Run hardening and audit tools like Bastille-Linux and Tiger and chkrootkit (and and not or or). Regularly update software including the kernel. Watch your vendors security bulletins.
Before you start, please check out the
LQ FAQ: Security references. Any security questions are welcome in the Linux - Security forum.