Install the openjdk
Copy and paste this into the terminal window (Click Applications –> Accessories –>Terminal)
sudo apt-get install openjdk-6-jre openjdk-6-jre-headless
Then just download the game to your home folder and run at the terminal
java -Xmx1024M -Xms512M -cp Minecraft.jar net.minecraft.LauncherFrame
If you have trouble you could try this, it appears as if the filename has changed. This is due to Linux being case sensitive.
java -Xmx1024M -Xms512M -cp minecraft.jar net.minecraft.LauncherFrame