The Conservative Party is interesting as it brings together a very shaky coalition of different political ideologies, mostly as a result of its history. The Conservative Party is actually very young, having been formed only in 2003 by the merger of the Canadian Alliance and the Progressive Conservative Party, and those two threads run often against each other within the Conservatives, with many defections the result of old Alliance members (Harper once led the Alliance) driving out the more moderate and urban old Progressive Conservatives.
Unfortunately, history is not all that useful in talking about where the political parties stand today. Saskatchewan was for a long time the bastion of the leftist New Democratic Party, but today they hold no seats there (partially as a result of district boundaries; they're in a reasonably close second in more seats than the Liberals there, but the Liberals do hold a seat). Quebec was historically a Liberal stronghold, then a Progressive Conservative stronghold, and is now a Bloc Quebecois stronghold (not as strongly as it has been historically for other parties, but realistically no party but the BQ will win the most seats or votes in Quebec any time soon).
In fact, provinces are prone to wild swings and misleading party identifications. PEI may look like a Liberal stronghold federally, but it actually is probably the most conservative province, save Alberta, and its Liberal strength is largely party loyalty. The Conservatives tend to do well in British Columbia, not because they are all that popular, but because the Liberals and NDP (and now the Greens) tend to split the left-wing and centrist votes all over the place.
I could rant more, but I won't.
Also, if you're interested in electoral statistics:
http://www.elections.ca/