How can I add a site search feature to a Jekyll Blog?
Jekyll + lunr.js = powerful full-text search, using JavaScript in your browser, for your Jekyll static website
One option to investigate Google Custom Search.
You mention trying to use Google in the past, but I'm not sure if you mean the custom search box as described here. Posting this in case it helps.