Although I have been to Canada a couple of times, I can't claim to know much about accomodation availabilty in that country. However, my general experience from all the places I have been to, unless some major event is present (like a huge conference or sport event), accomodation has allways been available to me. Even during peak seasons or during special events, if there are more than a few hundred beds for rent, somenone allways fail to show up for their booking, you only have to find out where. You might have to search a while, and you might not get accomodation at the quality level or price range you are looking for.Worst case you have to put in a couple of hours of extra travel to get to another place where accomodation is available.
Even when warned strongly against it, I have taken my chances. I have experienced having to sleep on the floor for a night as I came to a small ski resort place during the easter high season. Another time, on a small Island off the coast of Lombok in Indonesia, my wife and I had to sleep in a 1 dollar a night flee infested bungalow with a squatting toilet and something that resembled a roof and gave exellent view of the stars. I've also had to spend a night in a 4 star hotel when I aimed at a two star. In Thailand I had to live in an inexpensive but gorgeous bungalow right on the beach as it was the only thing they had available (the more expensive hotels were located further in on the island). Well, in all of the instances above I was warned against going without booking faaar in advance as I was guaranteed to be without roof over my head. In all cases I found a place to sleep, and the next day I was allways able to find pretty much what I was looking for (except for the bungalow on the beach which I chose to keep as it was a real treat). If you bring a tent, then you would need some really bad luck in order to have to sleep with no roof under your head.
Unless I plan to stay put in one place for more than a few days, I never book ahead as I enjoy the flexibility it gives me. I do however, if travelling far far away, like Thailand, book a hotel the first night. Then I can spend the following day to get adjusted and find out if I want to stay, find another place to live, or hit the road for a different place all together. Standing at the airport in a strange and unfamiliar country after 15-20 hours of travel, with all your posessions and eye boogers, and having to search for a place to crash for the night, simply sucks.
If you don't mind going either up or down budget for one or two nights from what you planned, then I'd expect that you would not experience any problems getting accomodation. I do however think you would be wise to checking out general availability of accommodation for the period and places you plan to go. Bring a phone and some listings and you can allways call and book from the road. If you anticipate that there might be some trouble in some area, you might want to try to book a few of days in advance (you might have to try a few consecuitive days). Worst case, you may have to wait a while or go somewhere else... I must admit however, searching for a place to crash after hours and hours on the road is not much fun. Call ahead if you are certain you will spend the night in some specific town. If you are very picky about accomodation (room with a view on street such and such, or the cheapest of the cheap, then allways book ahead).
Hopefully someone else here may be able to answer the general availabilty of accomodation on your route for the period you plan to be there. Regardless, placing some calls to a few tourist information centres along your route and a couple of hotels may give you an indication.
[This message has been edited by Wheelie (edited 04 March 2006).]