Olha Daniel a sua resposta depende muito do provedor, mas eu acessei o Jelastic me cadastrei e coloquei uma aplicação lá, onde a única coisa que eu fiz foi fazer o up no arquivo war, mas cada provedor tem sua forma, e tem muitos clouds com planos grátis pra você testar, em muitos deles é como o Jelastic.

Isso mesmo, Daniel. Também usei uma conta grátis num provedor "cloud" e só joguei o ".war". No meu caso foi o cloudbees.com.

Eu estou hospedando no Amazon EC2 e recomendo muito

O console de administração é muito bom - é uma página web, você fica meio perdido no começo, mas tem de tudo lá - dá pra alocar um ip estático, pedir servidor de smtp, banco de dados, etc

Eu tenho uma instancia small (que é free por 1 ano) e configurei ela conectando via SSH no servidor, dae instalei e rodei Tomcat via linha de comando.

Tem um esquema lá no console que fica bem intuitivo subir aplicações - você faz upload do .war via browser mesmo e já realiza deploy de tudo. Infelizmente não utilizei esse método pra falar mais =/