Several hosting companies now officially support Merb:

• Engine Yard
• Hosting Rails
• Dreamhost

If you are looking for a VPS, your best bet is to go with Slicehost or Linode where you have complete control. The most common configurations are Apache with Phusion Passenger or Thin on Nginx.

Shared hosts (with Passenger)

Merb on Slicehost tutorial