In the case of NixOS at least, 'immutable' doesn't mean you can't change the system at all.
It just means you cannot change the currently installed set of packages and services (generation in NixOS parlance); all you can do is create new ones and delete old ones.
Basically every update might as well be a complete reinstall of /usr, /etc and whatnot if you compare it to traditional distros.