Sticking extraneous data into an executable is straightforward if you have control of the compiler and are able to modify its code generator. You can play with the instructions, as mentioned; or put the message bytes into the text section and have the code jump around it; or encrypt the message, stick it somewhere within the executable, and set things up so that the decryptor routine is called only if the program is invoked in some specific way... the list is endless. Ken Thompson (one of the original designers of Unix) has an interesting discussion of this in his 1984 Turing Award lecture (http://cm.bell-labs.com/who/ken/trust.html).
It's a little harder for the vast majority of people who don't have their own compiler, but want to modify an existing executable file to embed a message. The quick summary is that adding bytes into an executable file causes addresses to change, and these changes have to be propagated throughout the file. The most obvious changes involve things like branch targets: if you stick some additional instructions into the text section -- even if it's a single NOP -- then you have to also adjust the targets of various branch instructions in the code to account for this; less obvious, but just as important, are the changes necessary to the meta-data, e.g., section header table entries in the executable. In order to update addresses, you have to be able to distinguish addresses from things that might look like addresses but aren't, e.g., bitmasks (notice that address updates aren't limited to the code regions of the file: pointers into the code in other sections, e.g., jump tables in the data section, also have to be updated). This is an undecidable problem.
Slashdot Mirror
It's a little harder for the vast majority of people who don't have their own compiler, but want to modify an existing executable file to embed a message. The quick summary is that adding bytes into an executable file causes addresses to change, and these changes have to be propagated throughout the file. The most obvious changes involve things like branch targets: if you stick some additional instructions into the text section -- even if it's a single NOP -- then you have to also adjust the targets of various branch instructions in the code to account for this; less obvious, but just as important, are the changes necessary to the meta-data, e.g., section header table entries in the executable. In order to update addresses, you have to be able to distinguish addresses from things that might look like addresses but aren't, e.g., bitmasks (notice that address updates aren't limited to the code regions of the file: pointers into the code in other sections, e.g., jump tables in the data section, also have to be updated). This is an undecidable problem.