-- Last Updated: Nov-11-11 8:55 AM EST --
Ontario Provincial Parks are about 90% self supported from the fees (some would say high fees) they charge for camping - probably an average of $15 per person per night. Non-residents must also pay a daily fee to camp on Crown Land (equivalent to National Forest in US)- so if the price of gas is a big issue for you, I'd guess the price of camping in the backcountry would be also. google for Ontario Ministry of Natural Resoursec - Provinvial Parks and you can find the fee schedules for backcountry camping.
A good source for you is "MyCCR.com" = Canadian Canoe Routes - look at the routes section for Ontario Forum.
Algonquin Provincial Park is likely your best bet for what you have described, but it is close to Toronto and can be quite crowded from what I hear - at least until you are a couple of days in, or unless you take a longer approach drive to the northern side. Likely entering and leaving mid-week is much less crowded, and "off season" - early May or Sept are better times to visit to avoid the crowds.
you did ask about Ontario - but Quebec offers lots of canoeing as well.