Method for finding correlation between data sets
Let's start with comparing two time series.  To compare them, you probably want to use cross-correlation.  The cross-correlation computes the correlation between signal $f$ and a delayed version of signal $g$, for all possible delays.  An efficient way to compute the cross-correlation is indeed by using a FFT, taking the product, and then applying an inverse FFT.

Now suppose you have $k$ time series.  I think the best you can do is to compute the cross-correlation between each pair of time series.  This requires ${k \choose 2}$ cross-correlation computations.