I'm not as familiar with how this is done with CLR, but it's probably very similar to how it's done with native code. When the compiler generates machine instructions, it adds entries to the pdb that basically say "the instruction at the current address, X, came from line 25 in foo.cpp".
The debugger knows what program address is currently executing. So it looks up some address, X, in the pdb and sees that it came from line 25 in foo.cpp. Using this, it's able to "step" through your source code.
This process is the same regardless of Debug or Release mode (provided that a pdb is generated at all in Release mode). You are right, however, that often in release mode due to optimizations the debugger won't step "linearly" through the code. It might jump around to different lines unexpectedly. This is due to the optimizer changing the order of instructions, but it doesn't change the address-to-source-line mapping, so the debugger is still able to follow it.