I know this has been asked here before, but none of the solutions have worked for me. I have a fresh install of Ubuntu 12.04 on my system and I installed Open Java 7 and I downloaded Minecraft. I right clicked Minecraft went to properties and set it as an executable and then went to open with and Java is no where to be found in the list. I made a new Java desktop file in /usr/share/applications and now when I go to the list Java is there and I set Minecraft to open with it by default but when I open it nothing at all happens. Now how am I supposed to get Minecraft to work?
In terminal type
java -jar /path/to/your/minecraft.jar, or you can run this Minecraft launcher. I have used it myself and will vouch for its effectiveness. It even will give you a nice menu icon.
Try going here http://modifyubuntu.com/ and search for Minecraft in the bar. Might help you, it's worth a try