The latest Angus-Reid poll (PDF!) shows that a $0.25 tax on every litre of gasoline has the measly support of 29% of Canadians. Interestingly, it's more popular in Alberta than it is in Ontario. (BC and Quebec predictably are warmest to the idea.)
Still, at 29% it's only a few percent less popular than our current government.