Ruby comes with a built in server WEBrick, though I have zero knowledge as to how it's set-up or indeed, how reliable it is. My understanding is, WEBrick can be run on a Linux or Windows server.

You'll need to contact various hosts and make sure their servers can accommodate an application written in Ruby on Rails. It will almost certainly be a Linux based host server.

I suspect you will find more than you think, as Ruby on Rails is becoming a very popular language. The only question mark, is whether your selected host has loaded the appropriate packages to run Ruby on Rails.

You can also run it on an existing LAMP stack, providing the Phusion Passenger module has been installed in Apache2 and as already mentioned, the appropriate packages.

The alternative is to rent your own virtual server and you can set it up how you like.