Canada Post keeps a tight reign on its claimed copyright of Canadian postal codes. The site 'geocoder.ca' referred to in the update is one of several sites that Canada Post has dragged into the Canadian court system. Basically, Canada Post makes money selling the information. Canada Post has gone so far and trade mark the spelling 'Postal code' (note the 'c' in code is lowercase). They claim exclusive right to this phrase.
Even while Canada Stats has data at the FSA/LDU level, the public data is ONLY available at the FSA level:
http://www12.statcan.gc.ca/census-recensement/2011/dp-pd/prof/details/download-telecharger/comprehensive/comp-csv-tab-dwnld-tlchrgr.cfm?Lang=E
The same copyright is true in US that zip codes are copyright property of the US Postal Service. But, in the US the crowd sourced and other reversed engineer compilations NOT derived from the USPS source, the USPS has never (and does not expect to) claimed copyright infringement.
And again, starting with the 2000 census the US Census stopped using actual zip codes and use ZCTAs (sort like zip codes - lol).
I have my own non-USPS derived compilations which I make publicly available (CC0) at:
http://www.opengeocode.org/download.php#cityzip