Heroku is a very easy option. In a plain server you usually have a ruby stack preinstalled, your provider should provide documentation about it, if you don't have a stack preinstalled you will have to install all stack yourself which is a lot of effort.
I would recommend you to try again Heroku, you could post your problem here in SO.
mod_rails is a plugin also easy to use when you have al the stack preinstalled and preconfigured. EC2 is a good option for this. Although is not as simple is this is written, you have to find and use a preconfigured stack which usually is not a problem.
I suppose you have a provider in mind, but this is the general flow.