What is a rootkit?
A rootkit is a set of tools that you run on a target machine when you somehow gained access to it with root-level privileges. The point of the rootkit is to transform that transient access into an always-open door. An example of a rootkit would be a modification of the sshd binary, so that it always accepts "8gh347vb45" as password for root, regardless of what the "normal" password for root is. It allows the attacker to come back later on, without having to go again through the hoops of the exploit he used first.
The first task of a rootkit is to hide itself, and to resists upgrades. If the rootkit merely modifies sshd (that's an example), the next upgrade of the openssh package will remove the rootkit. A more resistant rootkit would alter the package manager as well, so that when openssh is upgraded, the new sshd gets automatically modified so that the extra access point for the attacker is kept open.
The most powerful rootkits modify the kernel, which is the piece of software which actually manages the hardware. All process (for all users, including root), when they access data or hardware resources (e.g. reading or writing files), do so by asking nicely the kernel. A rootkit installed in the kernel can hide files quite effectively, and can reinstall itself upon every upgrade of the kernel, since such an upgrade would be the replacement of the file containing the kernel code with another one -- i.e. an operation which necessarily goes through the kernel.
A kernel module is a piece of code which is dynamically loaded into the kernel. In Linux, up to some point in the 1.3.x series, was a single monolithic block of code which was loaded in RAM by the bootloader in one go. Modules are chunks of code which can be added at a later point to the live kernel; their point was initially to allow the kernel to potentially handle hundreds of kinds of hardware without having to contain the corresponding driver code in RAM at all times. The idea is that when a new piece of hardware is detected on the machine, the corresponding code is loaded and linked to the kernel, as if it had been there from the very beginning.
The root user has the power to ask for a module to be loaded. So this is a way for some code with root privileges to get some arbitrary code inserted into the kernel itself, and running with the powers granted to the kernel, i.e. mastery over all hardware and processes (so-called 'ring 0' in the x86 world). This is exactly what a kernel rootkit needs.
Edit: as for the third question (can you patch against rookits), the generic answer is no (by construction, on a Unix system, root can do everything on a machine), but the specific answer can be yes. For instance, there are security frameworks which add constraints to what most root processes can do (e.g. SELinux), and can disallow kernel module loading. This means that the envisioned temporary root access by the attacker is not a true root access, only an "almost-root". Another possible feature is signed modules (the kernel would refuse modules which have not been cryptographically signed, so the rootkit would have to locate and use the private key before installing its own module, something which may not be possible if that key is not stored on the machine itself)(I am not sure whether signed module support is currently integrated in the Linux kernel). Also, modules must link with the kernel code, making them quite sensitive to variations between kernel versions -- so even in the absence of any actual countermeasure, it is difficult for a rootkit to reliably reinfect newer kernels upon upgrades.
A few things worth nothing when applying Tom Leek's answer to other operating systems:
- Although, kernel modules work differently on BSD, OSX and Windows, the relevant concept remains the same.
- Most drivers are contained in kernel modules. Therefore, sometimes kernel modules are indiscriminately (and incorrectly) called drivers. I find this especially true on Windows.
In the beginning the term "rootkit" was related only to NIX domain (root is not a casual word), but now it refers to every piece of software that allows you to gain "root" privileges in every OS. This software can be in user-space or kernel-space (so in the latter you need a kernel-module or a driver). Typically rootkits operates in kernel-space because it's easier to hide them and to delete their traces. But you could have a user-space application that exploit a buffer overflow in a privileged application that gives you root privileges!
But it's true: when we use the rootkit term we think to kernel code to gain high privileges.
Your following questions are very expansive to answer in this context. I think you can find them searching on Google for every argument. So for kernel module you have to distinguish Linux or Windows or Mac. The principles at the base are +/- the same, but you know that the Devil is in the details! :-)