Scott,
I paid Rim to Rim tours to take my bicycle gear and some food to the north rim. They were a great company to work with. I was allowed to store my bicycle in the gear room at bright angel lodge over night, and they picked it up themself from the lodge and drove it around. This allowed me to hike thought the canyon overnight and meet the shuttle at the north rim lodge the next day. They were also willing to lock up my bicycle at the north kaibab trailhead, but i decided it wasnt worth the risk and just hiked though fast to meet them. They also offered to drop some food or suppies of a jacobs lake, I didnt really have anything to send ahead, but this would be a nice option since there isnt much availible there.
I believe the maps on goggle are stored as Kml and I converted one and but in on my garmin in the past. So i do believe it is possible. If you cant get the file from the link i can send it to you.
I would say the road sections where less than 1/4 of the total miles. And where mostly as follows.
63 milesCannonville-Boulder. This could be greatly reduced by going farther north through devils backbone/poesy lake and the old escalante road.
35 miles Henry Mountains-Ticaboo/lake powell.
40 miles Halls Crossing-Natural bridges.
If I went this was again I would try and get around Lake Powell another way. There wasn't a ton of traffic, but it was all big boats and trailers. Theres a couple of ways that may be better.
One would be to follow the Hayduke route more from the Henry Mountains and go east on poison springs road then cut south down to Hite cross there and connect to natural bridges on forest roads.
Another option I thought of would be to take Hole in the Rock road from Escalante and hitch a boat ride across lake Powell. I'm not sure how easy that would be, but i bet you would get some attention being that far out by the lake on your bicycle.
As Far as carrying 3 gallons of water here is a picture of my bicycle after riding though the paria.
http://picasaweb.google.com/randinihill/UtahBorderToCarbondale#5236362124522982290Running front pannier gave me lots of room! There not as full as they look, just sloppy packing which is one of the nice things with that much room. As always I could have gone lighter, but I'm happy with what i had. Do to the lack of supply stops I needed to carry 3 days worth of food through a few sections and was still running low. 3 gallons of water was an overkill for sure. Since the Paria was flowing I didnt even need 1 and I didn't exceed one gallon at a time for the rest of the trip. The bottles on my bike total 3 liters. And I carried two MSR dromedary bags, 4 liter and 10 liter. I was also packing a 4 person tarp tent so i could have some shade if i needed. Two hiking poles for crossing the grand canyon and a back pack (empty on bike).
