Check out the royal college of physicians and surgeons of Canada website. You'll likely find a good number of answers there. My guess is that you'd have to take ("write" if you're Canadian) and pass some or all of the following exams: MCCQE 1 & 2, specialty board certifications exams. The other thing you may need to look into is that you have an adequate number of years of GME for your specialty and subspecialty.
How feasible is this? I do anesthesia and critical care.
As a general rule, you must be:
1) Canadian citizen
2) Have written / planning to write the relevant Canadian exams (as cbest outlined).
Jnut's advice is good: just talk to the provincial recruitment agency in the province / health region you're interested in working in (google physician recruitment [province]).
Where does it say that you have to be a Canadian citizen on the Royal College website?