(Full) N-key rollover means that you can press any arbitrary combination of keys on your keyboard and they will be registered properly.

So much for the part that is well-defined. If you intend to dig deeper, be ready to be confused.

We hereby suggest that starting from now (July 04, 2009), the following nomenclature be adopted Geekhack-wide:

x-key rollover (x being some integer) = x keys which are down simultaneously will register correctly under all circumstances, while anything more may not.

N-key rollover = Any subset of keys can be down simultaneously and will register correctly.

(If you're not interested in the gory details, skip to "Practical Limitations" now.)

"Rollover" is an archaic term from the world of typewriters. There it had a companion called "lockout" (see e.g. here).
N-key lockout meant: Once one key is down, all the others are blocked.
N-key rollover meant: Even if multiple keys are pressed at the same time, they will generate output in the order they were hit in.

When electronic keyboards came into play, which generally use keys arranged in a matrix to cut down on the number of connections, it all got more complicated. Without any special measures, matrix keyboards have some idiosyncrasies like the phenomenon of "ghosting" or "phantom keys", which effectively results in blocking after treated by the keyboard's microcontroller:

Blocking: The behavior that causes a certain key not to register because other keys are pressed down.

In addition, in order for the order of keys to be reproduced faithfully, the matrix scan rate must be high enough.

As per the definition adopted by e.g. US Patents 4420744 and 4794375,
no rollover is equivalent to N-key lockout (only one key at a time).
x-key rollover means that only the first x keys held down will be recognized and the others ignored.
N-key rollover means that any number of keys will be accepted correctly.
"Rolling" or sliding over thus merely indicates a key change without immediate release of the old key.

However, there are other definitions based on the notion of "rollover" being a condition in which they output may no longer be correct. This means that
x-key rollover = (x-1) keys which are down simultaneously will be registered correctly under all circumstances.
Therefore 3-key rollover as per this definition is equivalent to 2-key rollover as per the previous one.

"x-key rollover = any x keys will work" certainly makes the more straightforward definition.

In practice, it takes keyswitches with series diodes as well as matching keyboard controller firmware for full N-key rollover. Otherwise issues such as ghosting and masking will limit the combinations of keys that are accepted. (See basics on matrix keyboard scanning.) A normal matrix keyboard without any diodes achieves 2-key rollover, which means that not all the combinations of 2 or more keys will be accepted.

Now ordinary humans don't have more than 10 fingers, so basically 10-key rollover would be entirely sufficient.

When using a USB keyboard, an additional limitation comes into play: These only allow up to 6 keys plus modifiers (Ctrl, Alt, Shift, ...) to be held down at once, which is rooted in the protocol. This, however, is unlikely to be a significant problem in practice.

In addition, in order for the order of keys to be reproduced faithfully, the keyboard matrix scan rate must be high enough. A famous example with too low a scan rate is the Das Keyboard III with 10 Hz / 100 ms, with key transposition problems (indicating that the keyboard detected two keys at the same time and reported them in default order) still being reported occasionally by <100 wpm typists.
According to US Patent 4420744, "in a high-speed typing application a secretary is typically trained to type in 20 to 30 ms bursts" (e.g. "the"), therefore 50 Hz / 20 ms would be more like it.
The limiting factor towards the lower end is key bounce time, stated to be about 8 ms in this appnote, or 5 ms for Cherry MX switches. With overly fast scanning, the bounce would only result in excess keypresses being detected.

To test which combinations of keys are accepted, you can use this page for example.

For determining the rollover capabilities of your keyboard, you have to find the MINIMUM number of keys that will register properly when pressed at the same time. Try known-critical combinations like QWER, QWAS or QWSD for a start (outcome depending on keyboard matrix), or the QWAS/QWSD relative ASX (something that might actually be encountered in a game).

It may be worth noting that there are certain combinations of keys which will give keyboards with 2-key rollover trouble in that they block a large amount of other keys. Which ones these "evil combos" are would depend on the individual key matrix.
For older Cherry G80-3000 and G81-1000/3000 models (more recent ones are different), one example is ET. This blocks 2345, SDFG and XCVB along with W and R. Others include DG and CB. SD on the other hand blocks everything on the same row, including Caps Lock, Return plus numeric 4, 5, 6, ,/Entf (./Del) and Enter.
For the IBM Model M (and most Cherry models about 1998 and later), GH will block 4567, RTZU (RTYU), VBNM as well as F and J. TZ (TY) and BN are equally problematic. (Layouts: German (US).)

See this page for a reverse-engineered Model M matrix. (The 102nd key for ISO layouts seems to be on column a4 according to personal testing, possibly at a4-b1.)
Or see here for the Model-M-like Cherry matrix.

In general, you do not need N-key rollover. In many cases, a keyboard with a modest 2-key rollover is perfectly sufficient even for more demanding applications such as some games, as long as it doesn't use a very barebones (and/or badly designed) key matrix. A well-designed 16x8 (e.g. IBM Model M) or 18x8 (e.g. Cherry G80/G81-3000) matrix frequently does the trick. Obviously the matrix can never be optimized for all input patterns at once.

If in doubt, there is no way around finding out and testing the key combinations needed for the particular application - see Testing.

Applications that may place higher demands on rollover capabilities include:

• Braille2000 input (which requires up to 6 keys at once; according to the Keyboard Requirements, SDF + JKL must be accepted, ideally plus spacebar)
• emulating a musical instrument's keyboard
• some games