So, I have downloaded and installed java multiple different ways, but I cannot get minecraft to work. I really don't know what's going on, so I don't know how to explain it, but check out this video to see it in action: http://youtu.be/ZN9pmmjzqw0 If you would like to see the logs, they can be downloaded here: http://www.mediafire.com/?xgbxoe37gq79b
I think you have installed a Windows version of Java in Wine and it takes precedence over the "normal" Java from Ubuntu repositories, possibly only when you open Minecraft via a desktop shortcut.
You need to remove the Windows version of Java (if you have no other stuff installed in Wine I'd just remove/rename
Note the -jar parameter. Make sure you can run Minecrafr this way, and then you can create a desktop shortcut as described in the article linked to by MickStep.
You also don't need Minecraft.exe, and it won't work, don't even try.
Also, Minecraft works well for me with Ubuntu's stock-standard OpenJDK Java, so maybe you can start with it, and if it does not work look at installing Java from Oracle (but, again, not a Windows version)
Looks like you have installed the icedtea version of Java which is free software, however it appears you need to have the proprietary version of java to run minecraft, check out this blog post: