海外で（カナダで）クレジットカード作って、カナダのアカウントから引き落とししたいのですが、どこで手続きできますか？やったことある方、あるいはカナダでの生活が長い方教えてください。

自分の使っているバンクの携帯しているクレジットカードを作るのがよいのでは?

銀行に相談するのが一番でしょう
ただしこちらは自動引き落としというものはありませんから返済分は自分で振込みという形になります。 　

トピ主さんはカナダに来て間がないようなのでカナダでクレジットヒストリーはないのでは?
その場合クレジットカードを作るのはかなり難しいですよ、まずAMEXは無理でしょう

カナダにアカウントがあるということなので、そのアカウントがある銀行に相談するべきですね、その場合VISAか、マスターカードになるとおもいます
多分、その銀行に一定の金額を定期預金して、その定期預金の金額が上限の、セキュアカードを申し込むしかないと思います。
1年ぐらい問題なくそのクレジットカードを使っていれば普通のカードになって、定期絵預金も解約できます


　

>>自動引き落としというものはありませんから返済分は自分で振込みという形になります。

あります。
銀行の方(tellerではなく、financial advisorかmanager)に頼めばVisaにFaxで自動引き落としの申し込みをしてくれます。 　

Costcoに行けばAMEXは簡単に作れますよ。クレジットヒストリーのチェックどころかSINも聞かれず、主婦の私（収入０）にもミニマムの限度額からですが、カードが作れました。主人の収入や資産を聞かれたわけでもないです。
Costcoの年会費を払う必要がありますが、そういうところからヒストリーをつくるのも一つの道ですね。クレジットカード自体の年会費はありません。 　

　カナダのAMEXを申し込む時には、他にAMEXのカードを持っていないかどうか聞かれるので、そこに日本のカード番号を記入します。日本のクレジットヒストリーが参照されるので、限度額は日本での実績に合わせて一気に数千〜1万ドル程度まではすぐにもらえます。
　ちなみに、AeroplanPlus Goldは年会費120ドルだけど、15000マイルボーナスが付くのでなかなかお徳でした。
http://www.americanexpress.com/canada/en/aeroplan_splash_goldplat_interim_tribal_en.shtml

　TDやCIBCなど銀行系のVISAを申し込む場合には、残高がそれなりにあって、できればsaving accountまで開いてあるとスムーズなようです。所得や資産を詳しく確認されることはありませんでした。 　

皆さんご親切な意見、そして正確な情報ありがとうございました。
日本のように簡単にあらゆるところで作れるわけではなさそうですね。
クレジットヒストリーの審査が厳しいと多少やっかいではありますが、カナダのアカウントを持っている銀行に相談してみます。
ＣｏｓｔｃｏでＡＭＥＸ作れてしまうというもよい手段ですね。