> I know I have to delete all the markers from the map before the new
> markers are painted and I know I should probably be using
> marker.setMap(null);.
> I just don't know how and where to fit it in my code:
You can't, unless you somehow remember which markers you put on the
map in order to remove them later.
The usual approach is to store added markers in an array.
When you want to remove them all, iterate through the array and remove
each, then clear the array.
There are more sophisticated approaches, like checking 'new' markers
against 'old' ones in your array so as to avoid removing/adding the
same marker.