Homebrewing beer in Canada doesn't seem as popular as in the United States. Most Local Home Brew Supply (LHBS) stores are wine-centric and offer on-premise brewing of wine. These stores will usually have some basic beer kits but most are limited to beer in a bag or Liquid Malt Extract (LME) kits and don't offer specialty grains or hops. These stores will carry equipment kits for wine making, which can also be used for beer, but don't usually carry items that are more specific to beer.
If you want to evolve your hobby beyond the basic kits and create something with more character, fresher malt and hop profiles, and have more fun, then the average LHBS doesn't cover it.
In Ottawa, I'm lucky enough to have a chain of stores named Defalco's which carries a range of Dry Malt Extracts (DME), LMEs, malt, and hops. Their selection of equipment is fairly reasonable as well, except that they don't carry mash-tuns, lauter-tuns, boil kettles, or other more advanced equipment useful for all-grain brewing. Defalco's seems reasonably priced if you're just doing the occasional batch, but their prices seem much higher that what I've found on-line in the US.
This led me to seek out some on-line stores in Canada that can provide me with a better selection and value. I found these sites by searching through forums, search engine results, and homebrew magazine advertiser listings. Many of the sites that I found felt behind in terms of web design, which is also probably why they can be much harder to find than their US-based competitors.
Note that these descriptions are my opinion and based on my initial impressions after a quick browse of each site. Since I haven't purchased from all of these stores, I can't comment on their customer service.
I hope that this summary helps you find an on-line homebrew store that works for you. If you come across a site that I've missed, or one of these sites is no longer available, please contact me.
Update 2011-01-03: Since the Mashing Heads website is reported by Google as containing malware and because I've received a report of someone who's lost money from an unhonored order, I've removed this site from the article. Beware of this merchant.
Update 2012-02-19: Added Brewer's Pantry to the list.
Update 2012-03-02: Added Innovation Homebrewing and Beer Grains Supply Co.
Updated 2012-04-15: Added OntarioBeerKegs.com.
Updated 2012-04-18: Added Toronto Brewing.
Updated 2012-10-13: Updated OntarioBeerKegs.com. Removed HomeBrewGearCanada; site has been down for maintenance for a long time. Updated blurb.
Updated 2013-04-07: Added Clear Valley Hops and La Cachette Du Bootlegger.
Updated 2013-06-10: Added Hops Connect and BoasGrape Winery Supplies. Updated pricing for Clear Valley Hops.
Updated 2014-02-24: Added True North Brew Supply, Everwood Ave Brew Shop, and Mout International Inc. Moved to table layout; removed pricing information.