How to explain fractals to a layperson and to someone with more math training?

For a "high-level" explanation, I would say this: Fractals are surprisingly complex patterns that result from the repeated application of relatively simple operations/rules.

One of the easiest to visualize examples is the Koch snowflake, constructed by adding smaller triangles to each face of the figure at each iteration:

A more real-world example is the fern leaf. The DNA in a single plant cell encodes enough information to describe the structure of an entire leaf (and the entire plant, for that matter) without explicitly describing the location of each cell. Instead, the cells grow according to a set of simple rules that result in the self-similar appearance of the fern, even at smaller and smaller levels:

For a more complex mathematical explanation that still remains tied to the real world, have a look at the basic Ricker model of population growth and the resulting bifurcation diagrams:

_{(source: phaser.com)}

The x-axis on this graph is population growth rate and the y-axis is population density. Although it looks complex, All it takes is a handful of iterations of the basic formula on a hand calculator to see how the results can oscillate between seemingly random population levels.

That's easy. I would buy them some of this stuff:

(Then I would tell them to stare at it for awhile.) It's called Romanesco broccoli, and it grows like this for the same reasons, as explained in e.James' answer, that ferns do.

Alternately, I would tell them to check out Indra's Pearls by Mumford, Series, and Wright.

There are a lot of examples that are not hard to define rigorously, e.g. the Cantor set. This can be defined rigorously simply by taking a suitable intersection of nested intervals when the middle thirds are successively removed. It is easy to make all sorts of variants, constructing "Cantor-like" sets when you replace "middle third" with "middle fourth" or even with a construction where the ratio of the interval removed changes with the iteration. (This is important because you can then get a set of positive measure.) Leaving aside the remark about measure, all this uses nothing more than elementary mathematics.

One way to think of fractals is as of subsets of the phase space of certain dynamical systems. For instance, consider the Smale horseshoe. This is a two-dimensional map that can be visualized geometrically; this is explained in the Wikipedia article. Then the collection of points that stay in the square when you iterate this procedure both forwards and backwards is a fractal set, basically a two-dimensional Cantor set, which is very interesting from the perspective of dynamical systems (it's chaotic---one consequence of this is that knowing a point to arbitrary precision will not tell you what its orbit looks like later on with much precision). So much of the interesting behavior of dynamical systems is on fractals. You can define a map of the interval into itself such that the points in the interval that stay in the interval no matter how many times you iterate the map is just the ordinary Cantor set, as well.