All of these conditions are very important in algebraic geometry. I don't know much about the algebraic combinatorics aspect of these notions, but my feeling is that came from geometry and not vice versa.

The reason we care about these notions is that even though it would be nice to always work with non-singular varieties (a.k.a. regular) it can't always be done. For instance, families of non-singular varieties may degenerate to singular ones and most of the time there is no way to resolve these singularities in the families. 

For instance, any families of hypersurfaces (e.g., plane curves) degenerate to singular ones. However, hypersurfaces are Gorenstein so if we can handle those we are fine. So, in particular, to give an example of a Gorenstein but not regular ring you only need to find a singular hypersurface. For example $k[[x,y]]/(x^2-y^3)$ is such an example. 

Now if you study more general varieties than hypersurfaces you might not always be able to guarantee that they degenerate to Gorenstein varieties. On the other hand, if you consider stable families, then if the general fiber is smooth, then all fibers are Cohen-Macaulay. This is a non-trivial result. You can find it [here][1].

As Kevin mentioned, the Gorenstein and Cohen-Macaulay properties can be measured by the dualizing complex. $X$ is Cohen-Macaulay if and only if its dualizing complex is a sheaf and it is Gorenstein if and only if it is Cohen-Macaulay and its dualizing sheaf is a line bundle. I am not totally sure what he means by the last statement, but $X$ is regular if the sheaf of differentials is locally free. If it isn't regular one needs to think about what "top differentials" mean. For a discussion of that see [this MO answer][2].

Anyway, this gives us an easy way to construct Cohen-Macaulay but not Gorenstein varieties. You "only" need a Cohen-Macaulay variety whose canonical bundle is not a line bundle.
An easy way to do that is to use the fact that rational singularities are always Cohen-Macaulay. For surface singularities you can ensure that they are rational from their resolution graph (see Artin's [paper][3]) and it is easy to cook up a resolution graph that makes sure that the canonical sheaf of the singularity is not a line bundle. 

Another way to make sure that a singularity is Cohen-Macaulay is to compute its local cohomology. See Lemma 4.1 of this [paper][4] of Patakfalvi for a condition. That tells you when a cone is Cohen-Macaulay and then just pick a variety with the right embedding and it will give you something non-Gorenstein. For instance, take a cone over $\mathbb P^1\times \mathbb P^1$ embedded by the $(2,1)$ line bundle. 


  [1]: http://www.ams.org/journals/jams/2010-23-03/S0894-0347-10-00663-6/home.html
  [2]: https://mathoverflow.net/questions/35736/the-canonical-line-bundle-of-a-normal-variety/46663#46663
  [3]: http://www.jstor.org/pss/2373050
  [4]: http://arxiv.org/abs/1005.5207