According to Wikipedia: "A rootkit is a software system that consists of one or more programs designed to obscure the fact that a system has been compromised."
The perfect rootkit would be completely undetectable from within the infected system. That means antivirus software running on your rootkit-infected computer would not be able to detect the rootkit, which is, of course, the first step in removing it.
There are at least five types of rootkits, according to the Wikipedia article (firmware, hypervisor, kernel, library, and application level kits), but since the detection methods of each are radically different, we'll only look at a couple of them in this article. I'll also be assuming the Windows operating system for this article, although all operating systems are vulnerable to rootkit infections.
How to detect a rootkit
Since a rootkit, by it's very nature, tries to hide its own existence, they are not easy to detect. The only reliable method to detect one is to perform an offline scan.
That means you'll be running the scan from outside of the potentially infected system.
Most kernel, library, and application level rootkits are file-based, meaning they are contained in files stored on the hard disk of the computer. These are the easiest to detect with an offline scan.
In order to hide itself, the rootkit will modify Windows so that any file belonging to the rootkit will not be shown in folder or directory listings from within the infected system.
The flipside of this is that these files will show up in an offline view of the same folder locations.
One of the easier ways to do an offline scan is to build yourself an Ultimate Boot CD for Windows. This requires a Windows XP CD, and some knowledge. If you can't figure out how to build the CD from the instructions on the site, though, you probably shouldn't be looking for rootkits on your own. The potential for damage is significant, if you don't properly remove the rootkit.
NOTE: DO NOT build the CD on the potentially infected computer. The build process must be done on a known clean machine.
There is a program on the CD called Rootkitty. This is supposed to detect file-based rootkits, but it doesn't do a very good job. Instead, a little bit of command-line trickery is my preferred method.
What you're looking for are files or folders that show up when booting from the CD, but are not present when booting into the infected system.
Boot into the potentially infected system, and start the Command Prompt. In Windows XP this is done by clicking:
Start->Programs->Accessories->Command Prompt
In the command prompt window, type (pressing Enter after each line):
c:
cd \
dir /a /b /s > winfiles.txt
This will list every file on the computer, and store the filename and path in C:\winfiles.txt.
When this is finished, reboot the computer from the CD you created, and run a similar series of commands from the command prompt:
c:
cd \
dir /a /b /s > pefiles.txt
This will, again, list all files on the hard drive into C:\pefiles.txt.
Comparing these files will show if any files on the computer are hidden by a rootkit.
Your best bet is to transfer these files to a known clean computer and do the comparison there. There's no reason a sophisticated rootkit couldn't change text files that you were looking at to hide evidence of itself, either. Perform this transfer from within the Ultimate Boot CD. You can use a USB flash drive, floppy, or a network. This CD supports all three.
Now, compare the files using a program like Diffmerge, which will highlight any files that show up in one file listing, but not the other.
You will get some false positives using this method, so don't just haphazardly delete everything that shows up as different. Use your own good judgement and common sense.