I'd like to explore British Columbia, for maybe a few months. I see this being expensive and difficult without a visa, but I don't mind working, even in a stipend position that only covers living expenses.
What such programs, if any, are out there?
There is NAFTA, which if you are eligible makes it really easy to work in Canada as a US citizen. But the provisions in NAFTA don't apply to most people. "NAFTA applies to four specific categories of business people: business visitors, professionals, intra-company transferees, and traders and investors." "Professionals" is defined pretty narrowly; the majority of people would not fit into those four categories. You can't just go up and work on a farm or in a restaurant or something. (Computer programming would be eligible for example).
If you're not covered by NAFTA, you'll need a work permit. Exceptions are made for those working for foreign companies and such as well, such as airline workers; it would be silly for them to need a work visa every time they were on a Canada-bound flight. See http://www.cic.gc.ca/english/work/apply-who-nopermit.asp for more details on that.
There's a Working Temporarily in Canada page that leads to some good info, such as who can apply. In general, you need to have a company willing to hire you to sponsor you through this process. You can go as a visitor and find work, but normally would have to leave the country and re-enter on the work visa before starting work. The eligibility page says that you can't apply from within Canada unless you are switching jobs or are a student in Canada, but again I think you should be able to leave and re-enter.
In order to work in British Columbia as a Temporary Foreign Worker (TFW), an individual will normally need to get an Employer-Specific Work Permit. This usually involves obtaining a qualifying Canadian job offer from an authorized employer in British Columbia (or elsewhere in Canada) and may require that the Canadian employer receive a positive Labor Market Impact Assessment (LMIA). You mightfind it helpful to visit Canada’s Job Bank to search for open positions in British Columbia.