A system is said to be deterministic (in lay terms, "predictable") if it always produces the same outputs when the same inputs are given.
"Nondeterminism" is not to be confused with "randomness", which has a specific meaning in the context of retro games.
Determinism in emulation
Emulators are just programs, so they'll be as deterministic as the CPUs they run on.
Complications arise when the emulator uses multiple threads or multiple processes which need to be synchronised
(an enduring problem for software developers—read more on the English Wikipedia).
Additionally, an emulator may be called "nondeterministic" if movie playback desyncs just by making a savestate and loading it.
This is generally the result of how savestates are implemented (poorly-structured code, or simple programmer oversight) and not anything to do with the OS or compilation.
Determinism in console verification
In the context of hardware, "nondeterministic" can be used to mean "seemingly nondeterministic", or in other words, "having hidden or poorly-understood mechanisms". The microcontrollers and surrounding circuitry inside retro consoles are all solid-state with controlled tolerances; they always run deterministically, barring electrical faults or reliance on temperature-sensitive components. Optical disc drives are also a source of nondeterminism in modern consoles.