I have moved your question to the "Teaching English" section as it's more appropriate. There are people here with all kinds of experience so you should get some good info.
For my part, all I can say is don't consider Spain at the moment. I was lucky to have taught there before the recession really bit and when there wasn't a glut of teachers and not enough jobs. As a Canadian citizen you'll certainly need some extra paperwork if you head for Europe. What you need and how long it will take will depend on the country so you'll need to get the info from the relevant Embassy in Canada. What kind of job you'll be offered with a TESOL certification will also depend on where you choose to go.