As Joe said the answer highly depends on what you mean by information. I guess you don't mean the definition in computer science but are using it as the best word for expressing some intuitive concept.
But if your question is about how a simple rule can generate such a complex structure then the answer is because it is defined recursively, i.e. Mandelbrot Set is a fix-point as mentioned by Turkistany. Recursive definitions can increase the complexity of a set (membership of a point in the set, distance from the set, ...) considerably. The original equation over complex numbers is not very complicated, but recursive use of it (or almost any other equation) can create high complexity sets. So I would say that the complexity of the set is coming from the recursiveness/fixed-point.
I suggest having a look at the dynamical systems, fractals, and (mathematical) chaos theory books.
I would also suggest Mark Braverman's papers on computability/non-computability of Julia sets and his book with Michael Yampolsky: Computability of Julia Sets, Springer 2008.