You would have to ask an expert (which I am not) to get a better understanding, but to my knowledge there are two general classes of fractals.  The first (the type seen below) is a graph of a set of complex numbers. The most well known of these is the Mandelbrot set, whose mathematical equation is:

zn+1 = zn2 + c

where z is a complex number. There’s even a song about it:

The other type of fractal are the pathological monsters (so called because they exhibit what is known in math terms as pathological behavior): Geometric shapes that are self-similar and repetitive. An example is the Koch Snowflake, which is an equilateral triangle with smaller equilateral triangles stuck on each side, over and over infinitely. While building dungeons out of sets of complex numbers is impossible (or at least highly impractical outside of a computer), we can use the rules of these geometric fractals to simply and easily create dungeon maps that appear natural and highly complex.

Here are the simple rules:

• Create a simple shape, a tunnel, a cave, a district, whatever
• make a smaller version and stick them randomly or in an ordered fashion on the outside of or within the original shape (or both!) as appropriate
• repeat until your scale is small enough to stop or you’ve achieved sufficient complexity

And here are some examples. Click through to a larger version of each.

Here is a set of lava tubes, though it could just as easily be a branch of the world tree, an elven tree fort or a glacial fracture.

Here’s a set of caves. This was done by first using fractal technique for the caves themselves, then a second time for the tunnels.

This is a zoom in on one of the caves from above. Inside I’ve put a dwarven city. Some of the districts are in the main cave or some of the nearby smaller caves. Others districts and some paths between them are carved out of the surrounding rock.

That’s all there is to using the repetitive self-similar geometry of fractals to add some natural feel to your maps. Like fractals themselves, a simple rule set can create a high degree of complexity.

If you’d like to see more on fractals outside of gaming applications, here’s a link to a Nova documentary about them. Bring your popcorn though, it’s 53 minutes and you won’t want to pause it: