What criteria would I use to choose a server to run Node.js?
It seems like shared-hosting is a nonstarter since it's so new. Given how it works, what would I be looking at in terms of a production machine? Assume initially I'm on a limited (~no more than US$5 to US$25 per month) budget.
It is unlikely you'll ever see Node.js in a shared environment, because your Node.js processes run as long running processes rather than being instantiated via CGI or anything like mod_whatever under Apache.
This means you are looking at a dedicated server or VPS and even then you'll be at the top end of your budget. Something like Linode's smallest offering might be the best value you'll find with that budget - you can get cheaper, but you don't want to reduce your specification much further than that.
You might get away with less RAM, perhaps as little as 256 MB, but you are likely end up swapping so the I/O bottleneck of sharing drives with other VPSs will kill you then. You do sometimes see cheap old dedicated servers (lowish spec P4, 256 MB RAM, small drive) for US$25/month or even US$20/month - keep an eye on the offers area of places like WHT or more specific places like OLM's server-a-day if that is what you want.
The Node.js framework itself doesn't need much RAM or CPU power per instance due to its evented rather than threaded or process based architecture, but what sort of specification you will need will very much depend on what your code is doing (what sort of data processing?, how large are the data sets?, what database work?, how many concurrent users/processes are you expecting?, ...) so we'd need much more detail to be able to give you much of a more specific answer. Though with a maximum budget of US$25 it might be a case of taking what you can get and finding a way to live with it!
Edit: (2013-01-10)
Since writing that answer, prices/capabilities have changed quite a bit as you'd expect. There are in fact a few places offering Node.js hosting, and there are some very good standard prices on VMs (Linode is still a good recommendation IMO, but there are better value offers if you want to take the risk of a less well known provider) and small dedicated servers (from the likes of kimsufi.co.uk for instance).
But don't take hosting recommendations from relatively static pages like an Server Fault question without further research on discussion groups specific to hosting: the market changes so much that any answer here quickly becomes out of date, which is why shopping questions are generally discouraged.
Also check out a couple of Heroku-style Node.js hosting providers. They take away some of the burden of managing a machine and the Node.js process, while still being cost effective. Note that they're in beta status as of mid-May 2011.
MediaTemple's VE server is 25$/month (when you choose the yearly option, otherwise it's 30$/month), pretty good for a VPS with root access and 512 MB RAM.
Otherwise, you could make yourself a local VirtualBox webserver for free if you only wish to test Node.js and see if it's right for you before you start spending money on webhosting.
