A coherent sheaf $\mathcal{F}$ over a Noetherian scheme $X$ is called (maximal) Cohen-Macaulay if $depth_{\mathcal{O}_x}(\mathcal{F}_x) = \dim\mathcal{O}_x$ for any $x\in X$, where $\mathcal{O}_x$ is the local ring of $X$ at $x$.
Is there a simple example of $(X, \mathcal{F})$ such that $\mathcal{F}$ is Cohen-Macaulay but not locally free?
For regular schemes, I think they are equivalent. What about singular schemes? Under what conditions, a Cohen-Macaulay sheaf is locally free?
You are right. The Auslander-Buchsbaum-Serre theorem implies that the projective dimension of a CM module over a regular local ring is $0$ and hence a CM sheaf over a regular scheme is locally free.
It is quite easy to give examples of non-locally free CM sheaves.
(a) It is relatively easy to prove that if $X$ is CM, then $\omega_X$ is a CM sheaf. So, take any $X$ that is CM, but not Gorenstein. Then $\omega_X$ will be a non-locally free CM sheaf. Here is an explicit example: $$X=\mathbb A^3/(x,y,z)\sim (-x,-y,-z)$$ See this MO answer for a proof that $\omega_X$ is not locally free. The fact that this $X$ is CM follows from that it is a finite quotient.
(b) Let $X$ be a normal surface (hence it is CM) and $\mathscr F$ an arbitrary reflexive sheaf of rank $1$. Reflexive sheaves are $S_2$ and hence on a surface CM, but they're not always locally free. In fact, these sheaves correspond to Weil divisors while locally free sheaves of rank $1$ correspond to Cartier divisors.
So for these sheaves there is a criterion you are looking for: A reflexive sheaf of rank $1$ (which is CM on a normal surface) is locally free if and only if the associated Weil divisor is Cartier.
I don't know if there is an elegant criterion for a CM sheaf to be locally free. There is one result that is sometimes useful:
Let $f:X\to Y$ be a morphism with equidimensional fibers. If $Y$ is regular and $X$ is CM, then $f$ is flat.
In particular, if $f$ is finite, then $f_*\mathscr O_X$ is locally free.
Take any noetherian local domain $A$ of dimension $1$ and a finitely generated torsion-free $A$-module $M$. Then $\mathrm{depth}_A M=1=\dim A$. If $A$ is not integrally closed, then you have plenty of such modules which are not free (e.g. let $\alpha\in \mathrm{Frac}(A) \setminus A$ be integral over $A$, let $M=A[\alpha]$).
Proof of $M$ not being free. If it were free, then it would be of rank $1$ because two elements in $\mathrm{Frac}(A)$ are always $A$-linearly dependent. So $A[\alpha]=\beta A$ and then $\beta=1/a$ with $a\in A$ and $\beta$ is integral over $A$. This easily implies that $a\in A^{\star}$, thus $A[\alpha]=A$).
If $X$ is regular, then yes, locally free is equivalent to Cohen-Macaulay (see EGA IV, 6.1.5). In general I don't know a nice criterion ($X$ normal will not be enough).
