PIPEDA applies to federal works and undertakings across the country. If it's a bank, telecom, or transportation company, PIPEDA applies wherever you are. The provincial legislation does not apply. In B.C., Alberta, and Quebec, for provincially regulated organizations, those acts apply, and PIPEDA does not apply. In provinces where there is no provincial legislation, PIPEDA applies to the commercial operations of organizations. Nothing covers not-for-profits and so on.
On January 30th, 2007. See this statement in context.