Can't speak to the Lake Erie connector. The full description on the ACA site does address the question in general.
Along the canal, the stretch from Buffalo to Palmyra is described in the ACA Northern tier map, which indicates, in the commentary, towns with "hiker/biker" campsites. An example we used was at Middleport, where there is no signage, but if you ask at the police station (we arrived on a weekend and it was apparently closed, but soon enough a cruiser drove up - the ACA map also has a phone # which did us no good as we had no cell phone, and didn't know earlier how far we were going) they tell you where you can pitch a tent, and within 100m of that location there are a) cold potable running water; [outside spigot]; b) two unisex bathrooms with hot and cold running water, including showers; and c) a restaurant that serves a pretty good breakfast, with decent service, although not super fast. This (other than the restaurant), was free, with a donation box by the showers. Similar, but different, facilities exist in other small towns along the canal.
As far as frequency goes, to get something more than stealth, you could be looking at two hours ride in between. Passing Rochester takes longer, and you won't find anything in Rochester or the immediate suburbs. Camping-wise, that is. Rochester area hotels, motels, etc can be easily found on the web.
If you're interested in camping on the cheap, but want some level of facilities (i.e. not stealth), the ACA maps will be worth their purchase price for that feature. Commercial campgrounds tend to run in excess of $25.