Minecraft is one of those games, which run on Ubuntu natively. Of course you will have to have Java set up correctly. I'll show you how to do that in a short video!
Disregard the sloppy gameplay in the video, without screencasting, everything will run smooth.
You need to install Sun Java 6
sudo apt-get install sun-java6-jdk
The most important command i used is
sudo update-java-alternatives -s java-6-sun
because even if the the sun-java6-jdk/jre is installed correctly, another jre/jdk like openjdk may be the preferred version of java, preventing Minecraft from starting.
The command will set SUNs JRE as the default one and evade problems.