What is interesting/useful about CastelnuovoMumford regularity?
Here's how I think about CastelnuovoMumford regularity. It's an invariant of an ideal (or module or sheaf) which provides a measure of how complicated that ideal (or module or sheaf) is. This invariant is related to free resolutions, and thus it measures complexity from that perspective.
Why is it interesting? One answer is that it can be used to provide an effective bound for two famous theorems. The first theorem I have in mind is that the Hilbert function of a graded ideal (or a finitely generated graded module) over the polynomial ring eventually agrees with the Hilbert polynomial of that ideal (or module). The second theorem I have in mind is Serre vanishing, which says that, given a coherent sheaf $\mathcal F$ on $\mathbb P^n$, there exists $d$ such that $H^i(\mathbb P^n, \mathcal F(e))=0$ for all $i>0$ and all $e>d$. These two theorems are related: if $M$ is a graded module of depth $> 0$, and $\mathcal F$ is the associated sheaf of $M$, then the Hilbert function of $M$ in degree $e$ equals $H^0(\mathbb P^n,\mathcal F(e))$.
An example where CastelnuovoMumford is particularly useful comes from the construction of the Hilbert scheme (I have heard that this is related to Mumford's original use, though I have no reference.) The basic point is that you can parametrize the set of ideals with a given Hilbert function by considering subloci of certain Grassmanians satisfying determinantal criteria, whereas it's less clear (at least to me) how to parametrize ideals with a given Hilbert polynomial.
Another great example where CastelnuovoMumford is useful is presented in Eisenbud "The Geometry of Syzygies" chapter 4, where he solves the interpolation problem for points in affine space.

$\begingroup$ So your first theorem says that $H(M,n) = P(n), \forall n \geq reg(M)$ ? and this is the lowest bound ? $\endgroup$ – Andrei Jan 26 '14 at 20:02
Here's an example paper: 0905.2212
It uses some bound on Castelnuovo–Mumford regularity to prove that cohomology of smooth complex projective variety can be computed in parallel polynomial time.
http://
to this: en.wikipedia.org/wiki/Castelnuovo–Mumford_regularity $\endgroup$ – Anton Geraschenko Oct 4 '09 at 23:32