This is done using the javascript google mapa v3 api. It uses what is known as a custom overlay.
This will require Basic knowledge of javascript, and the HTML DOM.....
To add an custom image as an overlay, you simply create a new custom overlay object.
overlay = new google.maps.OverlayView(bounds,image,map)
You will need to define your options for bounds(where your image is displayed),image(location of your image file), and map(div on the map canvas).
If this is confusing to you, visit the Link below, which will help you understand better.
To add a search feature, simply create a new text field on your page, with a button, and add an onclick handler that will geocode the users input, (translate a input address or location into google maps latlng coordinates) and update the result to the map canvas.
For more on custom overlays:
https://developers.google.com/maps/documentation/javascript/examples/overlay-simple
For more on geocoding:
https://developers.google.com/maps/documentation/javascript/examples/geocoding-simple