Hardware secure keys are not a feature of Android, they're a feature of some (but not all) devices running Android, including most if not all high- and mid-end smartphones and tablets. The way they work depends on the capabilities of the hardware.
All processors based on an ARM Cortex-A core (and some older ones), whether 32-bit or 64-bit, have a feature called TrustZone, which is a sort of highly specialized virtualization. There are just two partitions: the secure world and the normal world. The secure world has access to the normal world, the normal world doesn't have access to the secure world. TrustZone itself isn't enough to do anything useful: the memory bus has to enforce the protection, which is the case on most (but not all) system-on-chips (SoC) based on a Cortex-A.
On a suitable processor, the secure world runs a trusted execution environment (TEE) with a small operating system. On reasonably modern Android versions, the keys of the Android keymaster are stored in the TEE, Android (even fully rooted) does not have direct access to them. There are phones where the device encryption key resides inside the TEE, but this isn't always the case.
The TEE data is stored encrypted using a key that Android cannot access. This key is derived from a root key which is stored in write-once memory (this can be fuses or other one-time-programmable (OTP) memory technology). The reason Android cannot access this key is that the processor ensures that it is only accessible to the secure world.
On some SoC, the secure world directly reads the memory. On other SoC, there is a dedicated component in the SoC that has exclusive access to the root key, and all the secure world on the main processor can do is to request a key derivation based on the root key. This doesn't change much regarding the security of the system: in either case, the key that the security of the system relies on is a key that gets stored in secure world memory.
Restricting the secure world to a derived key has one advantage: the key can be changed by changing the tweak on the derivation. An attacker who partially breached the TEE and managed to read data, but not to execute arbitrary code, would have access to the key. If the bug is fixed and the new TEE version uses a different key derivation parameter, then the attacker will no longer be able to read TEE data.
Some ARMv8 processors (including all high end phones today) have instructions similar to AES-NI, but this has no impact on security (except indirectly, in making cryptography less expensive and less prone to side channel attacks). AES-NI and the ARM equivalent are just ways to compute AES faster, the keys and data are still in the same place.