There are several mechanisms that could be used to record keystrokes. We'll be talking about a Windows PC for now, though the same general principles apply to any OS (though implementation differs in cases).
- Use a global 'shell' hook to record keyboard and mouse events
This is how most keyboard loggers are written and the easiest to implement. The author creates a DLL, and using APIs for catching hotkeys and such, it causes that DLL to be mapped into the process space of every process that gets user input. It then gets notified of every keystroke (or mouse movement if desired).
Symptoms: Unusual or suspicious DLL mapped into the process space of all top-level applications
- Low-level hook
This hook is harder to detect since it uses a filter driver to actually intercept keyboard events at the lowest level. These types of hook require higher rights to install, and can sometimes hide their presence.
Symptoms: Unusual or unknown device driver mapped into memory.
- Hardware hook
This is the rarest form of keyboard logging and actually involves a physical device attached between your keyboard and the USB or PS2 port it plugs into.
Symptoms: A strange looking device between your keyboard plug and motherboard.
If anyone ever cares, perhaps I'll write more specifically about how to detect them. However, the symptoms should make it clear what detection methods need to be done.