Just to elaborate a bit for those not familiar to Nix (slightly simplified to exclude recent support for content addressing). Nix work with derivations, a derivation is basically a data structure that specifies how a package is built. Derivations are normally not created by hand but using a function (eg.
stdenv.mkDerivation).
When you ask Nix to build a package, it hashes a normalized form of derivation data structure. This hash is useful in various ways, but one way it is used [1] is to look up whether the derivation is already in the Nix Store. Because if it is, there is no need to build it. So Nix looks up whether
/nix/<the_derivation_hash>
exists. If it exists, the build is done. If it doesn't exist and you have a binary cache configured (which by default is the binary cache provided by the NixOS project), Nix will look up the derivation hash in the binary cache. If it exists in the binary cache, Nix will download the path to the local Nix store. After that
/nix/<the_derivation_hash>
exists in the store and the build is done (without building anything). Only if that fails, Nix will actually build the derivation.
Now, one of the cool things about Nix is that it is derivations all the way down. So, it's not that just what we traditionally think of as packages is a derivation, but people wrap up all kinds of things as derivations, including configuration, etc. Since derivations are usually generated by functions, there are all kinds of useful functions that make derivations for eg.: single configuration files, scripts, etc.
In the end, building a NixOS system generation is just building a derivation. nixos-rebuild switches to a different generation by just setting a bunch of symlinks to an output path in the store containing that system generation (/nix/<system_config_derivation_hash).
At any rate, when you make a one-line change to a 200-line Nix configuration, Nix does have state to keep track of what it needs to rebuild or not. Nix will just try to build the derivation (and its dependencies), but it hashes the derivations, finds that their output paths are already in the store.
Some might argue that then the store is state. But it's not, at build time you are evaluating a pure function with memoization (the Nix Store).
[1] There is also a package name and version in the store path, but lets keep it simple.