Unless you are aiming at an international school, you're going to need a degree and license both granted from a Japanese university. That also (obviously, I hope) means very high language fluency, since you will be teaching in a public or private school here, and kids have practically zero English ability.
A couple of posters on GaijinPot web site have mentioned that they went through that particularly arduous route, so you might want to fish for them, if you are still interested.
A teaching license from Canada, plus 2-5 years of experience there, will make you eligible for teaching any subject at an international school (in English).