Google Maps, while not always reliable for bicycle routes, might be a good way to plan specifics.
But NY has a trail called Canalway Trail- Erie Canal Heritage Trail that will take you up from NYC to Albany, cutting across Upstate until you reach Niagara Falls / Buffalo. You can ride across the Peace Bridge, or Rainbow Bridge with your bicycle / walk, but I don't believe you can with the Queenston-Lewiston Bridge (furthest bridge north). Border crossing for people biking, or walking is really a short wait compared to driving over, so it shouldn't matter when you cross and there is no toll.
Once you're on the Canadian side, you're basically going to be mirroring the major expressway (and the lake) via Service Roads, which are well paved.
If you want a different route on your way back, you could go up further in Ontario to Kingston and then head south back into the States from there. It would definitely be the more scenic route and more rural.
Alternatively, if you want to go off the beaten path, you can just ride up until you hit the lake in NY. But once you cross over to Ontario, it's much more heavily industrialized than most of upstate / western NY (ie; anything near the water won't feel very 'natural'). If you did want to see some more awesome nature filled areas though, Hamilton, Ontario (which you'll be going through) has a bunch of beautiful conservation areas.
