today's compression technology is serious science indeed. Yes, the lossless compression in NEF is only almost lossless. I tested the compression performance in my D3 and the file size dropped from 25 MB to 15 MB. I use it all the time.
I don't know the details of the compression in NEF but consider this: first of two adjacent, almost identical pixels have one of the three 14-bit color components of the pixels different from the next pixel by one (of the 16 384 possible values). Having this type of difference would be almost impossible to detect in the image. Having for example, 10 such pixels in a row could be described by a structure of two members: a value specifying the number of identical pixels and the color. An uncompressed format would probably simply repeat all those identical pixel color values.
Another example: a text file can be easily compressed 90% without any loss of data. Everyone can test this using WinZip or some other compression tool.
Third example utilizes T3 packing algorithm inside the TIFF file format, used by B&W fax machines. It compresses a typical fax image (with a lot of white) close to 95%. An airline which I used to work for, compressed scanned boarding passes in T3 format, which resulted in almost unbelievably small image files without having any loss of data. For example, a 1664x1168 pixel image of a boarding pass is generally stored in a file of just 11 kB. An uncompressed file would require at least 237 kB (one bit per pixel).
Compression algorithms often assume something about the data. This way they can perform much better than for generic or random data. For example, a fax image with repeating black and white dots is very unlikely to occur but would, in fact, considerably increase the data size during compression.