VIA Rail will take bikes on trains with baggage cars only. There is a flat
fee of $15 ($30 for tandems) regardless of any transfers you have to
make, so even if you have to switch trains in Montreal, there is no extra
charge. The problem is that not all trains have baggage cars all the
time and your bike may have to wait for one. The "Ocean" which runs
from Montreal to the Maritimes always has one.
The steep hills in Quebec City are pretty short. You can "avoid" them by
sticking to the bike path on the rivershore to the lower city and walking
up to the upper city or by riding up the gradual incline on the Grande
Allée which could be quite busy with traffic.
is part of the
Route Verte. As for cycling along the Saint-John river valley, just follow
Route 144 to Grand Falls, 105 to Fredericton, 112 to Moncton, 134 to
Shediac. Take the coast road (950/955) towards the bridge to PEI. The
admin building where you take the bridge shuttle is on that road
towards Bayfield, just past the overpass at Hwy 16 (do not go on Hwy
NS route 7 is really pretty and offers classic Nova Scotia views of coves
and lighthouse points, much like route 3 to the south but quieter. No
shoulders mostly but the drivers are careful.
I'll be riding most of this route again from Ontario in late July as I'm
heading off to a highschool reunion in Cape Breton.