How do you sub-sample an FFT?
it seems like the bigger problem is that subsampling the signal would result in aliasing frequencies


No, subsampling in frequency domain corresponds to aliasing in time domain. So the idea here is to purposefully alias in time domain so that you get a sub-sampled FFT. That is exactly why 'Claim 3.7' of paper mentions $y_i=\sum_{j=0}^{n/B-1}x_{i+Bj}$. These are $n/B$ copies of $x[n]$ shifted by $B$ and overlapped. Each copy is positioned at $0,B,2B,\ldots,(\frac{n}{B}-1)B$. This aliased signal can be used to compute FFT ($B\log_2 B$ operations) to arrive at subsampled FFT. Total number of operations will the operations need to create the aliasing (summing of non-zero values of $x$ which equals $O(\text{supp}(x))$ in addition to the operation needed to compute FFT of aliased $x$ ($O(B\log_2 B)$). 

For example, if a time domain signal is $1024$ samples long, ideally you need $1024$ point FFT. But if you sub sample by taking every 8th sample, $B=128$, $n/B=1024/128=8$, the time domain signal at $\tilde{x}[0]$ will be having addition from $x[0]$,$x[128]$,$x[256]$,$\ldots$,$x[896]$. Like this for $\tilde{x}[n]=\sum_0^{7}x[128k+n]$. You can now use this $\tilde{x}$ to compute $B$-point FFT to arrive at the Subsampled FFT.