My text book doesn't seem to answer this question, just that it has to 'decode' the instruction, so it doesn't answer how it knows it has an instruction in the first place.
My research into this gives me possibly two answers:
1) It can't because both data and instructions look the same in memory, so it has to use the Program Counter to load the next instruction which may or may not fetch the next data it needs through addressing.
2) Something something opcodes something....
I'm trying to figure out a clearly understandable way of explaining this so I know I can understand it.
The processor fetches and decodes whatever memory is pointed at by the Program Counter.
The decoder can throw an "invalid instruction" exception if it does not understand the instruction. It will then jump to the exception handler (i.e., the OS), which will try to make sense of the invalid instruction. Often, it may just be an unsupported instruction that can be handled in software (e.g., floating point divide), and then execution can resume from where it had left off.
However, if it's a true invalid instruction, then the program will error out with some sort of exception/crash ("Illegal Instruction" on x86 I believe).
One technique to help separate code from data is to put them on different "pages" in virtual memory. The OS can then mark the page that the code sits on as "read-only". In this manner, a program trying to overwrite code will throw an exception. Some systems allow even more protection, such as "Fault on Execute" - throw an exception if you try to execute code on this page (More info here: http://www.tldp.org/LDP/tlk/mm/memory.html).
Things can get a bit weird though in that some code actually does need to be "modifiable" by the program (aka, "self modifying code"). This is made difficult because you typically have separate instruction caches and data caches. Typically, the instruction cache is oblivious to the world around it - it will have no idea that somebody has written new data to the addresses it contains. For some platforms, it is the job of the programmer to flush the i-cache after modifying the instruction data, so that the i-cache can refetch the updated instructions.
In the end though, it's the job of the programmer/compiler to make sure that the PC never jumps to any address that isn't code.
(Of course, malicious users will of course try to get the PC to jump to their bad code, but I'll save stack buffer overflow attacks for another post.)