When I was working at the University of Alberta last year, Ken Thompson came and gave an informal talk for anyone who was interested and he talked about this.
The gist if you don't want to read the article is you put code into your c compiler that checks to see if it's making the login command and then compiles in a backdoor. Nasty in its own right, but then you also put in code so if you recompile the compiler, it adds the code to do this (add the backdoor and add itself to the c compiler) back in. Then you take the code out of the source file and recompile.
Apparently it almost made it out into production Unix, accidentally. The only thing that stopped it was they had an error in their code that added an extra space each compile cycle and one of the QA guys caught it.
The gist if you don't want to read the article is you put code into your c compiler that checks to see if it's making the login command and then compiles in a backdoor. Nasty in its own right, but then you also put in code so if you recompile the compiler, it adds the code to do this (add the backdoor and add itself to the c compiler) back in. Then you take the code out of the source file and recompile.
Apparently it almost made it out into production Unix, accidentally. The only thing that stopped it was they had an error in their code that added an extra space each compile cycle and one of the QA guys caught it.