They pay for it. In fact the most common deal is to show both google search ads and google results, then the results are free and you get a cut of the ad revenue.