This guide provides steps for Ubuntu. You can install Ubuntu on your VPS from the VPS Control Panel.

Your standard Minecraft Server requires a Java environment, so let's install this first.

Since Java isn't on your standard repo list, we have to manually add it.

sudo apt-get install python-software-properties
sudo apt-add-repository ppa:sun-java-community-team/sun-java6
sudo apt-get update

After that, we can now install and update it.

sudo apt-get install sun-java6-jdk
sudo update-java-alternatives -s java-6-sun

The place where you install Minecraft is up to you (eg /home/minecraft/). After you moved to your desired directory, lets get the important files.

wget http://minecraft.net/download/minecraft_server.jar

To start your Minecraft Server use

java -Xms1024M -Xmx1024M -jar minecraft_server.jar nogui

You can lower the minimum/maximum of allocated RAM depending on your VPS specs. Once you start the server for the first time, some files will appear in the same directory. Settings can be changed by editing 'server.properties' with your favorite editor.

If you can't connect to your Server instantly, it might be due to IPv6. You need to start your Server like this.

java -Xms1024M -Xmx1024M -Djava.net.preferIPv4Stack=true -Djava.net.preferIPv6Addresses=false -jar minecraft_server.jar nogui

I recommend starting your server within a screen session. To start a new session, do the following:

screen -S minecraft

Once you are in, start your Minecraft server with the above command. You can leave the session by pressing Ctrl+A, D and reconnect to it by entering

screen -r minecraft