What is convolution intuitively?
I remember as a graduate student that Ingrid Daubechies frequently referred to convolution by a bump function as "blurring" - its effect on images is similar to what a short-sighted person experiences when taking off his or her glasses (and, indeed, if one works through the geometric optics, convolution is not a bad first approximation for this effect). I found this to be very helpful, not just for understanding convolution per se, but as a lesson that one should try to use physical intuition to model mathematical concepts whenever one can.
More generally, if one thinks of functions as fuzzy versions of points, then convolution is the fuzzy version of addition (or sometimes multiplication, depending on the context). The probabilistic interpretation is one example of this (where the fuzz is a a probability distribution), but one can also have signed, complex-valued, or vector-valued fuzz, of course.
I prefer sound to Terry Tao's light. Listen to my voice through a wall. At each moment in time, you hear not just what I am saying now, but also some reverberation from what I said moments ago. So if I make a sound given by $f(t)$ (density of air), you hear a linear combination $h(0)f(t) + h(1)f(t-1) + h(2)f(t-2) + \dots$, or a continuous version of that, i.e. $h*f$. The function $h(\tau)$ is how much you hear from $\tau$ seconds before the current time. If $h(\tau)$ decays slowly, my voice is muffled by reverb.
Fourier theory shows that recovering my voice $f(t)$ is difficult when $\hat{h}(\xi)$ is very small at some frequencies $\xi$: the wall doesn't vibrate at those frequencies.
If $h(\tau) \ne 0$ for some negative $\tau$, you can hear me before I speak!
What is the operator $C_f\colon g\mapsto f*g$? Consider the translation operator $T_y$ defined by $T_y(g)(x)=g(x-y)$, and look at $f*g(x)=\int_{\mathbb{R}}f(y)g(x-y) \, dy$. Rewriting this as an operator by taking out $g$, you end up with the operator equation $$C_f=\int_{\mathbb{R}}f(y)T_y \, dy.$$ This is only formally correct of course, but it roughly says that convolution with $f$ is a linear combination of translation operators, the integral being a sort of generalized sum.
Tying this in with Terry Tao's answer, which came in while I was writing the above, if $f$ is a bump function, say nonnegative, with integral equal to 1 and concentrated near the origin, then $f*g$ is a (generalized) linear combination of translates of $g$, each one translated just a short distance, hence the blurryness of the result.