What is interesting/useful about Castelnuovo-Mumford regularity? What is interesting/useful about Castelnuovo-Mumford regularity?
 A: 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.
A: Here's how I think about Castelnuovo-Mumford 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 Castelnuovo-Mumford 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  Castelnuovo-Mumford is useful is presented in Eisenbud "The Geometry of Syzygies" chapter 4, where he solves the interpolation problem for points in affine space.
