I'm not familiar with the Vezelay route but very familiar with the Le Puy route -- so this is a general response to your question. In France, the French mostly call a day ahead (so - Monday morning for Tuesday night) using their cell phones. That's singles and pairs. Larger groups would of course have reserved well in advance. And that is for the private gites. Municipal gites would occasionally fill up, and then the tourism office would locate other lodgings ... even resorting to private homes on one occasion for a friend of mine.
Easter ... or any of the other upcoming holiday weekends (May Day, V-E Day, Whitsunday) is likely to be a real challenge. First, they may be very long holiday weekends (Thursday through Monday is possible). Second, the French LOVE to go walking on those weekends. So make your reservations in advance for those nights ... now is not too soon for Holy Week and Easter.
Others with more specific experience are of course invited to chime in here.