Can we prove the Mandelbrot set is a fractal? Which maps/processes produce fractals? So, as you probably noticed, I have two questions. The second leads on from the first.
Can we prove the Mandelbrot set is a fractal? It is very easy to see that something like the Sierpinski triangle is fractal by design. Yet it's not obvious to me where you could even start to prove that the map which produces the Mandelbrot set creates this self-similarity, or even infinite detail.
Then, armed with this newfound (hopefully!) knowledge about the fractalness of the Mandelbrot set, the slightly more general question: is there a way to know which maps/processes produce fractals? E.g. some sort of test we can apply, in the case of iterative maps like the Mandelbrot set? (NB: proving such a test in the general case could be more difficult than proving the Mandelbrot set to be a fractal, but then it would be easier to apply). Obviously, as I noted above, there isn't much of a problem in the case of geometric constructions such as the Koch snowflake, the Sierpinski triangle, etc. The issue arises with algebraic constructions, such as that of the Mandelbrot, Julia sets etc. How do we deal with yet more types of construction, such as http://en.wikipedia.org/wiki/Weierstrass_function?
 A: Question 1
If you want to "prove" that the Mandelbrot set is a "fractal", then you'll need to work with some specific definition.  Under the characteristics section of the Wikipedia page on fractals, we see a couple of relevant points.  
The first clear definition of fractal was written in 1975 by Benoit Mandelbrot himself.  Specifically, a set is a fractal if its Hausdorff dimension is strictly greater than its topological dimension.  Even with the links, this is not a particularly easy definition to understand.  As it turns out, the Mandelbrot set is not a fractal according to this definition, as its Hausdorff dimension and topological dimension are both 2.  However, the boundary of the Mandelbrot set is a fractal, according to this definition.  The boundary of a set of topological dimension 2 is, perhaps not surprisingly, 1.  In fact, topological dimension is defined inductively in a way to make this statement almost a tautology.  Thus, the boundary of the Mandelbrot set has topological dimension 1.  The Hausdorff dimension of the Mandelbrot set is, in contrast, so complicated that it has Hausdorff dimension two.  This was proven in the early 90s and there is a copy of that famous paper on the arXiv.
Also under the characteristics section of the Wikipedia page on fractals, we see that Falconer advocates leaving the term "fractal" undefined.  In this sense, the term fractal becomes more of a topic, rather than an object, that gathers a number of themes together including dimension, self-similarity and related ideas.
Question 2
I don't think it's really a question of which maps produce fractals, rather, it's a question of how do maps produce fractals.
Consider iterated function systems, which produce self-similar sets like the Sierpinski triangle, for example.  These are simply lists of very simple functions, typically linear transformations - the very antithesis of what we consider to be "fractal".  A standard way to visualize a linear transformation is via it's effect on some set or sets in the plane.  The function $(x,y)\rightarrow(x/2,y/2)$, for example, shrinks the unit square by the fact two in every direction:

Now, if we combine that same transformation with two more transformations that also shift the set, then we can generate the Sierpinski triangle with an iterative procedure:

Now the point is that we are still using linear maps but it is the iterative procedure that creates the fractal effect.
Similarly, the Mandelbrot set is generated using functions of the form $f_c(z)=z^2+c$ where $c$ is a complex parameter.  These functions are studied in precalculus and, of course, they generate simple parabolas.  The Mandelbrot set, however, is defined as the set of all complex numbers $c$ so that the orbit of $0$ remains bounded under iteration of $f_c$.  Again, it is the iteration that creates the fractal effect.
Finally, the Weierstrass function that you ask about is not generated via an iterative procedure, but it is still generated a limit involving simple functions.  I guess the standard definition looks like:
$$\sum_{k=0}^{\infty} a^k \cos(b^k x) = \lim_{n\rightarrow\infty}
  \sum_{k=0}^{n} a^k \cos(b^k x).$$
I added the limit to emphasize the fact that the infinite sum is a limit of partial sums.  The sequence of approximations for $a=1/2$ and $b=4$ looks something like so:

