You have to purchase Minecraft from Minecraft.net, and make an account before you can install it. If you have an account, you can select to download the "Other Systems" file, which works with anything that can run Java. This is the version that we'll be using. It should be called "minecraft.jar" when it downloads.
Open your terminal, and run:
This allows you to run the .jar file. You are now able to do so. Right click, and select to open with a Java JRE. OpenJDK-6-JRE is the default, or you can install OpenJDK-7-JRE or use a PPA to get the official proprietary version.
chmod +x minecraft.jar
You can create a startup script for Minecraft. This isn't necessary, but this will allow you to do things such as have Minecraft as a desktop icon, and customize how you start it up later on.
A hassle-free startup script. Just put it somewhere and save it as a BASH script (.sh).
Congratulations! You're done installing!
java -jar /home/<username>/<pathtominecraft>
This is the simple and old-fashioned way to install Minecraft mods. No tools are needed other than a web browser, a file manager, a text editor, and the Archive Manager tool, all of which are already on your system.
This, of course, does not include mods that are only available through third-party tools, or rely on third party tools.
Download the mod you're going to use. You should get a .zip file, which you can then extract (unless it's a texture pack, more on those later in the tutorial).
You should now have a folder full of Java files.
Now navigate to "/home/<yourusername>/.minecraft/bin"
In this folder, there is a file called "minecraft.jar"
This isn't the file that you run to start the game, and should not be confused with it. Make a copy of it, and keep the copy somewhere where you will remember it. This will come in handy if you mess up a mod install.
Now right click on the minecraft.jar file, and select "Open with Archive Manager".
Select "Edit->Add Files..."
Navigate over to the folder containing the mod, go inside it, "Select All" (Ctrl+A), and hit "Add".
Now, still in the Archive Manager, find the META-INF file, right click it, and select "Delete."
You can now exit the Archive Manager. The mod should now be installed. Start the game normally, and the mod should be active (although you may not see any immediate clues).
These aren't treated as normal mods, because you keep them in the .zip file after you download them (unless it's a set), and treat them differently.
Download the texture pack, keeping them in the .zip format.
Move it into "/home/<yourusername>/.minecraft/texturepacks"
Open Minecraft, and go to Texture Packs. It will be in there, and all you do now is click on it.
Troubleshooting and Tips
If you're using a 64 bit installation, and you just get a black box when you try to log in, change your minecraft.sh script to be:
Change the script for whatever version of Java you're using.
java -jar /home/<yourusername>/<pathtominecraft>/minecraft.jar
FPS Is Really Low:
Make sure that your graphics card driver is installed. Run the "Additional Drivers" application:
Another option is to install the OptiFine Mod. It drastically improves your FPS. I used it myself and got tremendous success (gain of 2x).
If you think of anything I've missed, or want me to add something, please post or send me a message.