On Nexus devices, at least: CF Auto-Root works by unlocking the device's boot loader via fastboot (if it isn't already unlocked), then sending the device a custom boot image (kernel and ramdisk) that it should run instead of booting from the built-in system or recovery partition. It's analogous to booting your PC from a CD or USB drive instead of from the hard drive.
(This is a supported feature of the
fastboot program included in the Android SDK; it doesn't involve any exploits. If you look at the script that comes in the CF Auto-Root package, you'll see that it really just runs
fastboot oem unlock and
fastboot boot commands.)
Once the custom boot image is running, it has full access to the device (just like the built-in system software does), so it copies some files (the
su program and superuser APK) into the system partition. On recent Android versions (5.0+), it also makes some changes to the kernel's SELinux configuration that are needed to allow the root account to be functional. Then it reboots the device so that it'll boot from the (modified) kernel and system partition.