Consider a stone, it has a certain stone structure.
Now raise the scale, and you're looking at a rock.
Strangely enough it has the same structure on a larger scale.
Then rock formation, and ultimately mountain.

I turns out that nature is build of fractals, that is, things look the same regardless of scale.

The term is coined from "fraction" indicating a broken dimension.
That is, the surface area of a rock is greater than the corresponding sphere.
But if you look in more detail, you'll find that the surface area is greater still, up to infinity.
So the surface of a rock has a fractal dimension between 2 and 3.

Reading the article I get the impression that it's not a fractal geometry.
Space-time is divided into simplexes, which are basically tetrahedrons, and each tetrahedron is subdivided into smaller tetrahedrons.
In other words, is just a partitioning of space.
"Fractal" sounds very cool of course, but I don't think that's what this is. :(

We have to find a suitable definition of "dimension". The idea is to use the so-called spectral dimension which can be extracted from a diffusion process.

You can find some remarks regarding spectral dimension and CDT here:

http://arxiv.org/abs/hep-th/0505113 Spectral Dimension of the Universe Authors: J. Ambjorn (NBI Copenhagen and U. Utrecht), J. Jurkiewicz (U. Krakow), R. Loll (U. Utrecht)
(Submitted on 12 May 2005 (v1), last revised 6 Jun 2005 (this version, v2))
Abstract: We measure the spectral dimension of universes emerging from nonperturbative quantum gravity, defined through state sums of causal triangulated geometries. While four-dimensional on large scales, the quantum universe appears two-dimensional at short distances. We conclude that quantum gravity may be "self-renormalizing" at the Planck scale, by virtue of a mechanism of dynamical dimensional reduction.

A diffusion equation can be used to study the diffusion of a gas in D-dimensional space with a point-like source. This is a kind of delta-source which we need for the Greens function of the diffusion equation. From this Greens function we can calculate the return-probability of a gas particle after a certain time, i.e. we start the diffusion process at t=0, x=0 and check whether a certain gas particle returns to x=0 at t=T. Of course this return probability p depends on T and on the dimension D of space in which the diffusion process takes place, i.e. we have a function p(T,D). Analytically the diffusion equation contains the laplacian of D-dimensional space. From the analytical solution for the Greens function and the return probability p(T,D) one can determine D.

On graphs this does no longer work b/c there is no differential equation describing the diffusion process. First one defines a graph as the dual w.r.t. the triangulation simplices. Then we study a random walk on the graph which corresponds to the diffusion process. At each step t, t+1, t+2, ... the particle moves along one edge of the graph. Again we study the return probability at time t=T to the starting point. Then we apply the return probability formula derived for the continuum diffusion process to calculate D from p(T,D) extracted from the random walk.

Up to now this can be checked in a very simple way: use a D-dim. lattice, implement a random walk, count the steps for the return to the origin and calculate p(T,D). And of course one can generalize this algorithm for arbitrary but fixed (!) graphs. In this way one can define a dimension D for an arbitary graph G, i.e. D(G). This is the so-called spectral dimension.

What the CDT people do is to create samples for their triangulation, i.e. for their graphs (using something like Metropolis, importance sampling etc.), to extract the spectral dimension D(G) for each graph G and to calculate the ensemble average <D> for graphs contained in a certain ensemble. In that way one finds different CDT regimes for which there are different values for this averaged <D>.

It is this <D> derived via the scaling dimension for a "diffusion process on a graph representing spacetime" which shows somehow "fractal behaviour".

This dimension <D> must not be confused with the Haussdorf dimension typically used for fractals!