Debian is one of dozens of Distributions of the Linux/GNU operating system. You'd have to take a trip down memory lane to trace it's origin, but the short story is, the Debian distribution is one of several where the kernel of Linux and the accompanying software is packaged.
debian.org would be a nice cul-de-sac to visit for more information. fsf.org for the background on the rich history of GNU.
Hosts use (unless they're crazy) some distribution of Linux (Ubuntu / Debian / whatever) to host their services. If you buy "server hosting", you're really just buying the provision of a virtual host running Linux and their admins setup a ceiling of memory that virtual host runs within. So, for example the "2Gb" package means that the entire OS and your services (Minecraft in this case) runs in that allocation.
What I was trying to say before was, before you plunge into the world of hosting your server on a commercial service, you can experiment with your own box at home to get the configuration the way you want then copy the whole kit up to your new home. Getting the kinks worked out when you own the HW is a little better, IMHO. Most of the commercial operations I've seen provide McMyAdmin which allows you to use a web interface to monitor the server and perform basic system administration of the process and the underlying plugins (if any), to your setup. (More memory used, but minimal). It would be just as easy to setup a cron job to handle reboots and so forth if you want to run as lean and mean as possible; but if you're not familiar with Unix (Linux), I'd just go along with their simple Idiot-Proof McMyAdmin setup.
There are too many hosting companies, so just google for them. A little research can help choose the best one -- what is the traceroute from the potential service you want to use? If it's in BFE, then you my want to choose one that has a NOC that is centralized. Eg., if your players are US, and the server's in UK, I'd not advise it ;-) I don't know off hand which is "the best". What I look for is one that provides actual shell access. (Where I can remote login, not just ftp files). I want to be able to edit files on the virtual host (Old bearded Unix & suspender types like me need that).
$30 / month will probably get you 1.5Gb of ram in your provision. You'll probably blow through 700Mb - 1G just to run the server without players. That'll give you 500Mb left over to run MySQL (small 5-10Mb max, don't worry about it), and the OS itself (even smaller, not a concern).