For using the Search API Solr Search module, you first need a Solr server with the appropriate configuration files. For that, you have two options: either installing Solr on your own server, or purchasing a server instance at a Solr hosting provider.
The most important thing to remember, for both variants, is to configure the Solr server with the correct configuration files (see below).
Using a hosted solution
Using a hosted solution has the big advantage of requiring no expertise in Solr. There are a number of Solr hosts which either support the Search API directly or allow you to upload your own configuration files. A few of them are listed on the Search API Solr Search project page, but the list is surely incomplete (and might also be out-dated). One thing to watch out for (except for either explicit support of the latest version of Search API Solr Search or support of uploading custom configs) is that the connection shouldn't require any advanced authentication mechanism, like a certificate or appending GET parameters to all requests, as this currently isn't supported by the module (out of the box). Currently, only Basic HTTP Authentication and HTTPS are supported.