I'm learning about DEP implementations, now I'm trying to figure out how does the OS know which part of memory is
intended to hold data only?
In an executable file, the bytes are organized into sections. Traditional names are "text" for a section which is meant to contain code, and "data" for a section which is meant to contain data. There is also "rodata" (read-only data), "bss" (read-write data initialized with zeros)... Thus, the OS knows what access rights to give to each page. The names given here are more from the Unix tradition, but the same concepts apply to the Windows world.
Then the application will allocate further memory chunks for its own usages. By default, the OS gives back data blocks (read and write access are allowed, but not execution, at least if DEP is enabled). The application can then explicitly request a change with VirtualProtect(): interpreters for some programming languages with JIT must do that since, by definition, they dynamically produce executable code and then proceed to execute it right away.
The OS keeps track of the intended access rights for each page, but it does not "guess": it obtains the information from either the file which is to be executed (it is part of the format) or, for dynamic allocation, the application itself is supposed to provide the information.
Any executable file contain only two types of instructions: the data and the code. Typically, data will be the initialized and uninitialized variables within a program while code will be the program instructions processing and manipulating those variables. When the executable file is mapped in memory, the data sections are mapped to stack and heap while the program instructions are mapped to the .text section of the program.
If you think about it, there is no way the program instructions are ever going to change during the execution of the program therefore, the .text section is always mapped as readable and executable. Also, no legitimate program will ever want to execute something from a data section of a program because it contains only initialized and uninitialized variables that is stack and heap are always mapped as non executable (only readable and writeable). That is why whenever DEP detects any executable instruction from either stack or heap, the program is terminated. Executable instructions are only allowed from the .text section of the program.