I've done this quite a few times already. Either DE brings in all the deps it needs. For Cinnamon simply install the package "cinnamon". For MATE install the package "mate-desktop-environment".
I have not had to install Gnome 3 before installing Cinnamon. You do have to bring in a couple of basic things like the gnome-terminal package. I outlined some of my Cinnamon adventures in another post that I'll find and link. MATE is a complete and very polished DE at this time, more so than Cinnamon. Cinnamon seems to have a few more rough edges.
I'd highly recommend starting with a Debian base vs Ubuntu server. I use a Squeeze 6.0.3 Live ISO to start my installs. I have the version that just installs a basic shell environment. The Live ISO is a great Debian package to start with as it's designed to be burnt to a CD or USB stick using something like Unetbootin. Much easier to use than many other Debian installers. 10 minutes to install, then change the sources to what you want and away you go. I've used both Debian wheezy or Mint LMDE repos as sources, I can post my source files and preference pinnings if you'd like.
Regardless of the main repos I use, I always include the Mint packages repo so I can get the great font rendering Mint and Ubuntu have, plus I like to use the MDM login manager that's only found there AFAIK. Installing this brings in all the X stuff you'll need, too.
EDIT: Here's the thread where were talking about running pure MATE and Cinnamon desktops.
viewtopic.php?f=200&t=99741&start=20The thread is about running an LMDE-Stable setup but about halfway down this page we branched off into this topic.
One thing I'll add to my info above re: MATE, I found recently that I could not use the repo from packages.mate-desktop.org when using the Mint LMDE sources. There must have been enough updates in the MATE repo to make it incompatible with Mint's snapshot of Debian testing. I haven't tried Mint's MATE packages against Debian testing either as I tended to prefer the newer packages in the packages.mate-desktop.org repo. However, I just built a MATE box yesterday using purely Mint sources that is really running sweetly. Everything works together so well. It's a testamint (<- that's a pun

) to Mint's UP philosophy.