It's easy to hide code on both Windows and Linux, and on every other OS that I know of. Once malicious code gets into your machine, there's really no way to guarentee that it's ever gone. If anybody asks me what to do after they get a virus or something, I tell them to format. That's the only way to be sure.
The trick is, to hide code, you generally need to do kernel modification (a rootkit, or kernel module, or system driver, or anything like that). On Windows, every use (almost) runs as Administrator, so any malicious program can do that. On Linux, most users run at the user level, so it would be harder to hide malicious code. But still possible, though, since you can hide malicious code (as a few examples) as a Firefox extension, as a Gaim plugin, and probably a dozen other places. But at least, when you're a user, you can't hide it in program executables (infecting /usr/bin/ls or C:\windows\sytem32\explorer.exe, or wherever explorer is, is evil).
To summarize: if you're running as root/administrator, on either Windows or Linux, there are tons of places to hide evil code, it's game over.
If you're running as a user, it's more difficult, but still possible.