The idea is to generate Perlin noise from a deterministic 2d random function. For a given (x,y), this function gives a random number between 0 and 1.
The average of the interpolated value of this function at different scales gives Perlin noise. Then, different levels of noise are associated to different colors.
See https://web.archive.org/web/20160421115558/http://freespace.virgin.net/hugo.elias/models/m_perlin.htm for details.