Needed: introduction to FFT
I found the following review paper very illuminating:

Fast Fourier Transforms: A Tutorial Review and a State of the Art
by P. Duhamel and M. Vetterli.

It covers a lot of things, from history to implementations.