Searches are a feature of Views. Ignoring maps for the moment, you would create a View with the search filters you want to include. You output the fields you want to display in the results, e.g. the post titles linking to the posts themselves.
Bringing Maps into the equation, the map is simply displaying the results (as markers on the map), it isn't responsible for the search itself, it just takes whatever posts the View spits out and uses them as the source for the markers.
In the newer blocks UI, you add a View block to a page and set it up with the custom search. If you don't want to list the results (you only want them on the map) you don't include anything in the View output.
Then you add a Map block to the same page, and specify the View block on the same page as the source for the map.
If you were using the legacy interface it works slightly differently, inasmuch as the search is still set up as part of a View, but in the output of the View you insert the map itself (outside the Loop, so it appears only once) and the markers (inside the Loop) via shortcodes, using the Fields and Views button.
If you have more specific details about where you are stuck we can give more targeted guidance.
