Handbrake is an open source, GPL-licensed, multiplatform, multithreaded video transcoder, available for Mac OS X, Linux and Windows. I recently switched to Linux Mint 13 and the MATE desktop environment.
This article shows you how to install Handbrake on Ubuntu or Linux Mint.
$ sudo add-apt-repository ppa:stebbins/handbrake-releases
$ sudo apt-get update
$ sudo apt-get install handbrake-gtk