Software

Here is a pseudocode courtesy of wikipedia.
The FFTW Home Page: A fast C library for performing the FFT in one or more dimensions, including parallel and real-data transforms.
The FFTW code implemented in python courtesy of Henry Gomersall.
Jörg's "Ugly" Page: Jörg Arndt has gathered a self described "bucket" of FFT links and source code. As the desciption indicates, the page is wanting in organization but not in depth.
Rosettacode.org has source code for performing the FFT in a plethora of languages.
Paul Bourke's website has a tutorial on the DFT and code for the DFT and the FFT.
A codeproject.com tutorial by João Martins.
A java FFT implementation courtesy of Douglas Jones and Columbia University.
Another FFT code in java courtesy of the computer science department at Princeton. The goal of this code is to optimize understanding of the coding rather than to optimize the computational speed of the code.
The faster than fast Fourier transform (aka the sparse Fourier transform) page at MIT and the direct link to their source code. The code is intended for research purposes only, and is not a stand alone library.
Chris Lamont's C# FFT code with extensive comments.
Several different implementations in Fortran and C courtesy of Intel corporation.
The FFT implemented in visual basic by Xavier Flix based on an earlier visual basic implementation by Murphy McCauley found here.
An FFT implementation in Ruby courtesy of Greg Johnson.
An FFT implementation in php by Matthew Binkley.
Nayuki's website has a tutorial on the DFT and code for the DFT in several languages.
Manish Kumar Bhojasia's website has Java code for the DFT using the FFT algorithm.

Software