There's no error message telling you you can't hack an extra vhost into httpd.conf, but once you've got paged at 3am because your hack disappeared, you pretty quickly learn to supply your own error message.
Heroku's an extreme example of this - the dyno filesystem is perfectly writable, but it's definitely going away within 24 hours.
(The large-company version of "all configuration is produced by automation", which produces a surprisingly similar result, is "all configuration is produced by another team".)
The first piece of the puzzle is to present configuration to runtime processes in a read only manner and enforce this rule from the remote side (e.g S3 bucket where the machine only has a R/O key or R/O NFS mount). For added points you can make the OS image read only (but that's another post).
The second piece is to make sure that you have easy build automata that can push into that repository easily and reliably. This is really key - you have to have a programatic way of doing things.
same in programming... unsafePerformIO, dropping into native code or assembly, etc. In 2013 the hardware exposes a mutable interface.
In programming, it's a conscious decision to break immutability (assuming a language that supports it). It administration, it's a conscious decision to enforce it.
Chad claims that they throw away the ssh-keys to the machine. So they don't actually have root. Or maybe that was a goal that hasn't been reached yet, don't remember exactly (Chad gave a talk in Berlin on this and related topics).
In C, it's possible to change a const. But const is still a very valuable construct, even if it is possible to cheat.
val x = 1; x = 2;
is an actual error and the compiler/runtime will give a "you can't do that".
Immutable infrastructure, on the other hand, would require read-only enforcement on all aspects of configuration. It can be done, but not easily, and someone always has root. So what you're really talking about is the ability to reconstruct an environment programatically from scratch, with no manual intervention, which is laudable but not exactly immutable.
This is the sort of thing that makes me appreciate the 12 Factor App idea (http://www.12factor.net). Rather than trying to make configuration immutable, make it impossible. Don't rely on the existence/continuity of a filesystem at all. Don't use configuration files.