Ubuntu and Mint are based on the same core distribution, Ubuntu, and therefore have mostly the same underlying repositories for software and supporting libraries. At the time of this writing however, the latest version, Linux Mint 12 is still based on the previous Ubuntu version 11.10. Linux Mint 13 is scheduled for release in May 2012 and that version will be based on Ubuntu 12.04.
The major difference between Mint and Ubuntu is the default choice of user interface. Mint's default interface is the Gnome-shell interface with the Mint Gnome Shell Extensions (MGSE) installed. MGSE was developed partly in response to the Gnome user community's negative reaction to the release of Gnome-shell which radically changes the user experience as compared with the previous Gnome 2.x interface. Ubuntu has developed their own interface called Unity. Fedora 16 uses the Gnome-shell interface without any special extensions.
There's been a great debate around the user interface since the release of Gnome-shell. Previously, Gnome 2.x was available on all major distributions. Now, modern distributions come with Gnome-Shell and Gnome 2.x is not available. Gnome-shell does have a fallback mode that looks a lot like Gnome 2.x, but a lot of tweaking functionality is missing out of the box.
In the past, I've written about my views on the subject, but over time I've grown to accept the Gnome-shell interface as the best choice for me. However I need to point out that Ubuntu's Unity interface seems to work on any hardware, while Gnome-shell only works on suitably modern 3d-capable video hardware. In the absence of such hardware, fallback mode is used. As for Mint, I've had the worst experiences of all, having the most trouble getting Gnome-shell and MGSE working.
Gnome-shell is also available on Ubuntu, easily installable using a simple command (see my article: HOWTO: Setup Gnome Classic on Ubuntu 11.10).
The other major difference between the distributions is the currently supported Linux kernel version. As of this writing, Mint is up to 3.0.0-17, Ubuntu is up to 3.2.0-24, and Fedora is up to 3.3.2-6. What does this mean to you? Maybe not much, some of the features in the newer kernel versions apply to advanced use cases that you may not care about, however there are some kernel features that translate into better performance. Whether or not you keep up with what's new in newer kernel versions, staying up to date ultimately has its advantages.
Personally, I don't like the Unity interface, I prefer Gnome-shell. And, in the absence of good video hardware (or when running Linux inside of VMware player which currently doesn't allow gnome-shell to work), I use Gnome-shell fallback mode. Since it's possible to attain this configuration on all three distros, this doesn't help much in making the choice of distro.
My favorite distro is Fedora. Why? It's hard to say. Between the fact that it is running the most recent kernel of the three distros, and the fact the the default interface is pure gnome-shell, and that it uses RPM and YUM like Redhat Linux does makes it a good choice for me. Fedora doesn't look all that great out of the box, but a few tweaks can make it look really good (see my article: Good Looking Fedora Tweaks).
Ubuntu 12.04 LTS will be supported until 2017, while those of us running Mint or Fedora will have had to upgrade to newer versions several times before then. So, if you are building a Linux system that you don't want to mess with for several years, Ubuntu 12.04 is the way to go for now.
My plan is to play with Ubuntu 12.04 and continue to use Fedora 16 as my mainstay, until Mint 13 and Fedora 17 are released, at which time, we'll do this all over again! Such is Linux...