Sinatra is a micro-framework for making web applications using the Ruby programming language. Calling it a micro-framework might actually be overkill. Actually, it can be thought of as a domain specific language for building dynamic websites and web applications.
Sinatra is spawn many similar projects using different programming languages. Its DSL is simple but powerful. You've probably seen a demo before:
get "/hi" do "Hello World!" end $ curl "localhost:4567" Hello World!
Most shared hosting services will gladly state if they support Ruby on Rails because of the framework's popularity. Unfortunately, not many will publicly state whether or not they support Sinatra.
Fortunately, if a web host supports Ruby on Rails, chances are they also support Sinatra. The preferred setup to run Rails applications is Apache with Passenger for shared hosting. Using Passenger means the web host is setup to run any Rack based applications, which means Sinatra will work!
If a service supports Ruby on Rails with Passenger, it will work with Sinatra. If you're still unsure, contact their support staff.
Dreamhost is recommended if you're looking for a shared hosting service that supports Sinatra. They use Apache with Passenger, so the Rack-based Sinatra applications will work fine. Dreamhost also includes unlimited bandwidth and storage, along with tools like Git. Having unlimited private Git repositories is a huge benefit!
WebFaction is hosting for developers. WebFaction is what I personally use. Their servers aren't as crowded as other services, meaning resources aren't limited and websites aren't as slow. They also tend to support bleeding edge technologies quickly. They were one of the first hosts to officially support tools like Rails, Django, and Git. Official support means you can contact their reliable support team when something goes wrong. Sinatra applications can be setup using WebFaction's point-and-click control panel.
Heroku is becoming the de-facto standard for running your Rack-based applications. Setting up an application is as simple as pushing to a remote Git repository. It's also free to start with one application server. Scaling up is as simple as using their web based control panel. Scaling up tends to be more expensive than if you're using bare-bones EC2 instances or VPS/dedicated servers, but it also requires less maintenance since you won't have to patch or update your own server software.
See Ruby on Rails Hosts for a list of hosts that supports Ruby on Rails. All of these hosts also support Sinatra applications.
Dreamhost supports Sinatra via Apache/Passenger.Check out Dreamhost