Are fractals and chaos theory related, both historically and math-wise?
(Please keep at least parts of your answer in layman’s terms, if possible.) 
Yes, chaotic algorithms are used to produce fractals.
Basically, yes, though there are wrinkles.
Broadly, as a concept fractals greatly predate chaos theory. While the name wasn’t coined until Mandelbrot (I think he first introduced it in his book Les objets fractals in 1975), particular examples had been known since the likes of the Cantor set and the Koch curves/islands in the late 19th century and the Sierpinski gasket (1915-6). These and some related ideas tended to be regarded as oddities until Mandelbrot highlights them, unifies them under the notion that becomes called fractals and comes up with lots of other examples. One should, however, be slightly cautious; this standard account of the prehistory of fractals owes everything to Mandelbrot and one suspects future historians may come up with different emphases.
Independently, you have the prehistory of chaos theory. This has been less throughly discussed, but there are various rough anticipations of it. The main idea is usually taken to be “sensitivity to initial conditions” aka the Butterfly effect. There are several different sets of ideas through 20th century physics and mathematics that are akin to this. But it remains for an historian of science to pick through these stories and see exactly how these came together as what came to be called “chaos theory”. (This is up there with a biography of Wolfgang Pauli as my suggestion for the book that needs to be written on the history of modern physics.)
That said, the standard start of chaos theory is Edward Lorenz’s 1963 paper on instabilities in an atmospheric model. But Lorenz couldn’t explain why his model was unstable. It was simply an observed feature of his computer runs. However, in the early 1970s, David Ruelle makes a connection between this type of instability and fractal attractors. Very roughly, a system’s attractor is where that system wants to be. Now if the attractor is simple, then the behaviour is simple. The classic example is a pendulum being slowed by the air. To work this out exactly would be terribly complicated, but the end result of the motion is simple: the pendulum winds up at rest. It’s been attracted into this state. Mathematically, the attractor here can be represented by a single point. Very simple. And unchaotic.
Fractal attractors are not simple. By their nature, anything fractal is very jagged. And if you move ever so slightly on something jagged, then it changes by a lot. Systems with fractal attractors don’t settle down into a simple state. They settle down into an irregular one. Where even small changes make a big difference to subsequent behaviour.
So there’s a connection between fractals and chaotic behaviour that became apparent in the 1970s. Is that the end of the story ? Not quite. Some people suggested that fractal attractors in a system become a definition of chaos. That’d be the nice elegant, neat conclusion. But there were big, big arguments. The outcome was that it was decided that there were several reasonable definitions for a system being chaotic. In particular, some cases were found where systems are considered chaotic, but which don’t have fractal attractors.
I believe it’s true to say that chaotic systems usually have fractal attractors. So there’s a close link, such that the two subjects are related in most cases.
There’s a final historical wildcard. The French mathematician Henri Poincare (1854-1912) got very, very close to inventing chaos theory, including hitting on the idea of fractal attractors. If he had, the two historical strands would have converged much earlier.