We did not carry any paper maps with us whatsoever.
I did a fair amount of detailed route planning for the trip up, and for the first day of the trip home. As with laying out routes for driving, the first step was to put the proposed stopping points into Google Maps and ask it for directions. Then I spent a fair amount of time in "terrain" mode which, when zoomed in far enough, gives you elevation contours. Dragging the route around in Google Maps let me balance climbing vs distance for various possible routes through the mountains. Google Street View is very much incomplete in rural areas but it does exist for some roads and you can look down bikepaths and non-covered sideroads from the intersection to get some idea whether they really exist and whether they're paved or not. For each day of riding I probably spent at least an hour in Google Maps looking at the roads, maybe more.
Once I was happy with the route, I entered it into Gmaps Pedometer and saved the map number in a spreadsheet. Then I imported each ride from there into mapmyride.com, which can import from a large number of formats including directly from gmap-pedometer.com. Mapmyride.com can also export to .kml (which gmap-pedometer can't) and it can make an elevation profile and add up the total climbing for the day (though it does not seem to include all of the climbing in the total, so if you wanted a precise amount you'd need to export as CSV and do the calculations in a spreadsheet). Finally, I imported the .kml URL into "my maps" in Google maps again, from where I could view the map as a layer in the native mapping application on my Droid. What's nice about this process is that at no point do you have to download and re-upload data files to the computer you're using to access these tools. Another pleasant surprise was that mapmyride.com has elevation data for Canada, which Gmaps Pedometer doesn't.
This left me with exact, optimized routes which we followed pretty much as written the whole way to Montreal, with one exception. I'd found a bike path that looked like a really great way to get the last few miles into town, but I wasn't sure that it really connected, so I'd used it only on the way home and found another, less gorgeous route for the way there (figuring that while there I could confirm whether it worked). But at the end of the second day of riding, at an ice cream stand in Vermont, we ran into some cyclists from Montreal who were doing a big loop through New England, and they confirmed that the path actually connected. This combined with adding a night in a hotel that happened to be along the ride home and not along the northbound ride meant that once across the border we ran my planned first-return-day ride backwards -- so it was handy that I'd laid it out in that much detail in advance.
Following the route on the phone was not as easy as following a route on a printed map, for a bunch of reasons. I don't have a handlebar mount for the phone, so checking the map meant stopping, usually at any confusing intersection. Even if I'd had one, I'm not sure the battery would have run long enough to keep it running the whole time, and the power button is small and fiddly so I might well have had to stop anyway. Mapmyride.com's distance markers are incredibly inaccurate, which made it hard to tell how far a turn was. The native Google Maps app does not have a scale bar, and it was not until sometime yesterday that I figured out how to get it to give me distances. The Droid can acquire GPS pretty quickly for a GPS receiver, but that's still a fair fraction of a minute, which seems like a long time with traffic going by. It helped to spend some time in the morning looking over the ride so I'd be familiar with the turns, and it also helped to write out directions with mileages on the back of a receipt so I could clip it to the bike.
I signed up for all-you-can-eat data for Canada with Verizon from the road and they were incredibly helpful. Coverage was awesome, especially in Canada (where it's flat) but even on remote dirt roads under tree cover at the bottoms of little creek valleys in Vermont. I had an extra-thick ziploc bag I borrowed from desiringsubject and using the phone through it basically worked. I carried a spare battery but never needed it.
The big thing that didn't work was expecting to be able to lay out routes for the return with as much care while we were in Montreal. The theory was that we'd have a better idea then how much challenge we were up for and in fact this did affect our route plans pretty significantly. But even so I should have spent more time last month looking at the roads paralleling route 7 in Vermont, or route 12 in New Hampshire -- I had some idea that I'd be considering them, and knowing more about them ahead of time would have helped a lot.
Not having this planned out ahead of time meant that we did a lot more ad-hoc route planning of the "oh look, the road ahead is unpaved, let's see where the road to the right goes" type -- and a whole lot more getting lost, because once we abandoned the (rough) plan I'd put into Google Maps for the way down, we didn't even have mapmyride.com's inaccurate mile markers to tell when to expect turns. We wound up getting lost several times between Middlebury and Ludlow, which added at least five unplanned miles to the ride.
Buying rim tape in Ludlow, the owner of the bike shop bent my ear for 15 minutes about all of his favorite roads, both in the direction we'd come from (he was especially fond of one of the roads we'd wound up on by accident, which I have to agree was quite lovely) and in the direction we were going. He was a little bit of a nut as far as liking hilly unpaved roads, but I got great information from him as to what was paved and what wasn't, and what had good shoulders, and where the climbs were and how bad they were, which was worth way more than that much time with Google Maps would have been. In the end he described a route for us as far as the Massachusetts line that will now be my default cycling route to and from my grandfather's place, and I ended up using the map function of the phone just as a map, and not to display the route at all.
I'm tempted to get a handlebar bag with a clear top and a solar USB charger for the phone, to see if that changes the way I use it at all. I definitely learned a lot -- albeit some of it a little too late -- about how to navigate from a phone without getting lost. And if we get Cartman working again I'll probably go back to printing out maps, at least sometimes. But multiday rides without paper can totally work.