I'm looking to find a VPS service, providing me with a low cost, hosted, Debian package.
I'm unfamiliar with the OS, and, after looking at several offerings, I'm not entirely sure how I can best compare them.
What kinds of questions should I ask from a hosting provider, in order to know which one is providing me the most bang for my buck?
(I'm looking at providers which allow root access/complete control over the hosted image)
Debian itself doesn't cost money. An entry level VPS is likely going to set you back about $20-40 per month.
There are many providers that can do this. I suggest you have a look at some of the more well known providers such as AWS, Linode, Rackspace, VPS.net etc
Each Operating System has it's own set of advantages and disadvantages, it's really hard to compare them for you as it depends on a number of factors (what you're familiar with, support, what you want to use the OS for, security implications, ease of use etc).
I'm assuming you want to run a web server (or mail server or similar). Debian is a good fit for that and it's widely used. It's a stable OS that has a lot of care taken to make sure packages are stable and secure.
If you want more information about Debian check this out: http://arstechnica.com/information-technology/2008/12/why-ubuntu-users-should-care-about-debian/
That article also introduces another OS, Ubuntu. Ubuntu is a derivative of Debian (so they're very similar). Ubuntu it quite popular and you may find it to be advantageous to you as it generally has more up to date packages and a really welcoming community (particularly to new comers).
It's worthwhile doing research online, to see what others are saying. A great resource (if you're in Australia) is http://www.webhostingtalk.com.au/