The Teensy page is interesting but links to a description of a pre-installed bootloader. I was interested in how to program the thing if it had no bootloader for some reason. Or just to discover its device signature.
The LadaAda page is also interesting. I hadn't spotted that one.
From what I have been able to gather so far the low-level programming uses two pins (Reset and PDI_DATA) where you basically shove serial data (8 data bits, 1 stop bit, even parity) through those two pins using Reset as clock and PDI_DATA as both Tx and Rx using two x 220R resistors to allow communications both ways.
It seems that you follow a fairly specific timed protocol of sending stuff down the reset pin, and then 0x1289AB45CDD888FF (lol) to enter external programming mode.
I recently discovered that all the signature bytes for the Atmel CPUs are listed in the CPU data sheets available on their web sites (search the PDF for "signature"). I have not found a consolidated list anywhere, but here are the ones relevant for this thread:
Device Device ID bytes 2 1 0
ATxmega16A4U 41 94 1E
ATxmega32A4U 41 95 1E
ATxmega64A4U 46 96 1E
ATxmega128A4U 46 97 1E
They all agree with the codes listed in your board programming software