Decide which OS you want (centOS/Debian), install a firewall, make sure you are on a DDOS protected server (you know the kiddies will get ticked when they get caught "cheating" and then start "attacks"), make sure you have plenty of RAM (if you want a large "game") on the server, install Java and then pick the flavor of the Minecraft server... basically. I looked at doing it, but decided since I don't play the game I had no real interest in running one.
I think you may need to find the IP of the server. A popular way to do this with other people is to download Log Me In Hamachi and the Haguichi GUI (atm Hamachi is commandline only for Linux)
Go to https: // secure . logmein.com / US / labs/, go down to Hamachi for Linux, download the .deb, install through Software Centre as normal
Download haguichi by doing this in the Terminal
sudo add-apt-repository ppa:webupd8team/haguichi
sudo apt-get update
sudo apt-get install haguichi
then click the ubuntu icon at the top of the screen and search for haguichi and launch it.
After you have done this
press f2 and note the ip address.
Launch the MC Server .jar
Type the ip address you wrote down into the Multiplayer tab of Minecraft.