The same way AMD added 8 new GPRs, I imagine: by introducing a new instruction prefix.

Yes, two in fact. One is the same prefix (with subtle differences of course, it's x86) that was introduced for AVX512's 32 registers. The other is new and it's a two byte extension (0xd6 0x??) of the REX prefix (0x40-0x4f).

The longer prefix has extra functionality such as adding a third operand (i.e. add r8, r15, r16), blocking flags update, and accessing a few new instructions (push2, pop2, ccmp, ctest, cfcmov).