Algolia makes it really easy to add search to your site.

They offer a variety of plans for different use cases, and their API can be accessed easily using client side JavaScript or server side languages. Even with the client side code, they make it possible, and fairly simple, to setup searches for private data (making sure a given client doesn't get search results from someone else's data).

Algolia offers a Jekyll plugin, which makes it dead simple to submit the data from your Jekyll site to a search index. They also offer a free plan, which has some hard, but relatively high limits. You have to show their logo in the search interface if you want to use the free version.