first check the log files. some root kits are smart enough to clean
them up, but most of the time there's useful information about the level
of compromise and source. absence of logs is also a clue. ;)
if it's a root-level compromise, you can no longer trust any of the binaries on the machine. it's common practice to install custom binaries to hide cracker activities. therefore, we bring our own disk of clean binaries on a write-protected floppy. haven't yet seen things like hacked kernel modules that would require a separate rescue disk or anything like that.
guess and check to look for the files that the cracker may have installed, this is typically a total shot in the dark, but there are some tricks, such as looking for file names with spaces, regular files in /dev, and files with mtimes/ctimes in the right time period for the breakin. many root kits come with linsniffer which generate a log file with a consistent name (tcp.log).
retrieve all the interesting files from the machine for later analysis. in partiular, we take syslogs so we can do followup with the attacker's isp, sniffer logs so we can run them through sparse (or whatever other parsing tool we have) and handle any passwords that need changing, and the root kit and exploit code so we can keep a library of such things, and because we're computer geeks and like to see how these things work. ;)
tell the user to reinstall the machine and give them pointers to security patches for linux. we also have a one-sheet that talks about some quick ways to get some security improvement. ----