The term has two meanings.
In it's original meaning in the book, it is a malware program that an attacker uses to replace a legitimate program - like a cuckoo laying it's eggs in another bird's nest .
More specifically, it was a replacement for atrun, which is executed every 5 minutes - meaning the attacker had to wait at most 5 minutes before his malicious code was executed. Stoll refers to this as the "hatching" of the cuckoo's egg.
From pg 123 of "The Cuckoo's Egg":
I watched the cuckoo lay its egg: once again, he manipulated the files in my computer
to make himself super-user. His same old trick: use the Gnu-Emacs move-mail to
substitute his tainted program for the system's atrun file. Five minutes later,
shazam! He was system manager.
The other meaning of the term is a music file that has a contents other than it's title suggests, put on file-sharing networks in an effort to combat piracy. See the footnote in the Wikipedia article about Stoll's book.
In both meanings, it is a file whose contents is different from what is expected.
