If you try multiplying two numbers, say 4 digits each, using the standard grade school technique, you'll see that you end up writing the digit-wise product of each number, with a shift (adding a zero at the beginning) for each digit, followed by a sum. This is literally just a convolution operation over the digits (this is because secretly writing a number in base B is equivalent to expressing a polynomial evaluated at the integer B, and multiplying polynomials is a convolution over the coefficients). By the convolution theorem, this O(N^2) time operation can therefore be accomplished in O(N logN) time by doing multiplication in frequency space and then transforming back. This is because the Fourier transform is O(N logN), via the FFT, and multiplication is O(N).

I just looked up the answer to my original question - the Fourier trick is notionally only O(N logN), but because the FFT takes you from integers to floating points, as N gets larger you need to encode more and more bits to achieve enough precision to yield absolute errors <1 after doing both Fourier transforms. The need to encode those extra bits tacks on another logN, taking you to O(N log^2 N).