I think they mostly use free parking spaces (though I expect they also need a city permit to serve food). That's the thing about parking in Manhattan: it's either really expensive, or it's free. So a substantial portion of traffic at any given time is cruising around trying to find a free parking spot.