Fully automated decompilation is not possible -- this problem is theoretically equivalent to the Halting Problem, an undecidable problem in Computer Science. What this means is that decompilation cannot be achieved for all possible programs that are ever written, and that the separation of data and code is hard to achieve. Further, even if a certain degree of success is achieved, the generated program lacks meaningful variable and function names as these are not normally stored in an executable file (except when stored for debugging purposes).
Some people believe it is only possible to recover the assembly sources, this in itself is not a trivial problem, again, due to its equivalence to the Halting Problem. However, in practice, there have been approaches to deal with disassembly and decompilation. The more successful ones make use of extra information (e.g. knowledge of the compiler used) or require human input at the hard parts of the disassembly process.
A good example of actual decompiling of X86 machine code to C is given on the dcc home page. FermaT, by Software Migrations Ltd, is an industrial strength program transformation system used to migrate IBM 370 Assembler modules into equivalent readable and maintainable COBOL programs, and to help solve the year 2000 challenge for IBM 370 Assembler code.