Understanding Genkin-Pipman-Tromer's ground potential, side channel attack on RSA
How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits?


Actually, they're jumping to secret bits; however those aren't the secret bits you're thinking of.

The bits displayed above are not the actual bits of $p$ and $q$.  Instead, those are the bits from the secret exponent; because GnuPG uses CRT (and apparently binary exponentiation), those bits are of $d_q = d \bmod p-1$ and $d_q = d \bmod q-1$ (where $d$ is the private exponent).

With the CRT optimization of RSA, we take our message $M$, and divide it into $M_p = M \bmod p$ and $M_q = M \bmod q$.  We then compute $C_p = M_p ^{d_p} \bmod p$ and $C_q = M_q ^{d_q} \bmod q$ separately, and then recompute $C_p$ and $C_q$.  This attack looks at the computation of $M_p ^{d_p} \bmod p$ and $M_q ^{d_q} \bmod q$, and attempts to recover $d_p$ and $d_q$

So, what good are those bits?  Well, those are as good as the actual values $p$ and $q$; with the knowledge of those values (actually, we only need one of the two), and the public key, we can factor.

The actual technique to factor using $d_p$ does use some simple number theory; I'll sketch it out for you: with your known value $d_p = d \bmod p-1$ and the public exponent $e$; because of how RSA works, we have the property that $x^{e \cdot d_p} = x \pmod p$ (for any $x$), while no such relation holds $\pmod q$.  So, what you do is select a random value $r$, and compute $r^{e \cdot d_p} - r \bmod n$.  This value is 0 mod p, and (with high probability) nonzero mod q; hence doing a simple gcd with that value and $n$ gives you the value $p$


  I expect that jump is highly dependent on GnuPG's RSA implementation.


Yes; this sort of attack won't work with more recent implementations (such as OpenSSL), which disguise these sorts of simple side channel attacks.