Boondocking is possible, in Canada, on Crown Land - our equivalent to BLM land. I believe the limit is 21 days.
There are several maps available online that show Crown Land. I am not sure if there is much of it in the more populated areas that you'll be traveling to, but it's always worth investigating. In principle I think it's a great idea.
Here's the link to the provincial maps for Nova Scotia.
http://www.novascotia.ca/geonova/hom...e/ns_atlas.asp
Edit: having just read the provincial site, I am not sure if their camping policy is as generous as in Ontario - they don't mention camping at all, just hunting and fishing. I'd ask around.