There's two issues involved.
Statements like "I hate all [minority group]s" aren't considered a hate crime in Canada. We do have a tradition of free speech, after all.
However, statements like "kill all the [minority group]s", which advocate immediate violence, do violate our hate crime laws.
It gets blurrier when considering statements like "I'd love to watch a [minority group] die", or holocaust denials.
It isn't clear from the article that the holocaust denials themselves were an issue in terms of his deportation. His "links to neo-Nazi and white supremacist groups that espouse violence" (emphasis mine), are more likely to be the issue here.
Committing significant crimes in Canada (including hate crimes) is one thing that will usually cause a landed immigrant to have his/her status revoked.
The other issue, as I understand it, is that to my knowledge, Canada has an extradiction treaty with Germany.
That means, if German laws are broken (which Zundel has apparently done), and that the death penalty (or other form of punishment Canada considers unethical) is unlikely to come into play, then Zundel can be extradited if the evidence against him is sufficient to warrant a trial.
None of these steps occur summarily. Zundel's right to due process was respected at every step of the way.