Normally, you don't need to mail your passport right away. They first process your online application, and then request your passport only when/if you're approved-in-principle. You would then send it to http://www.cic.gc.ca/english/information/offices/missions/sao-paulo.asp (or there may be visa processing centres throughout Brasil, I'm not sure).
Disclaimer: I've only dealt with Russia, the process for Brasil may be different, you should read the rules online.
As for how long it takes: I only have experience with the Moscow office, but I had a great experience with it. I've seen two applications where the visa was approved in 4 working days (that's 4 days until they sent the passport request, plus the mailing time of the passport back and forth of course), even though the official waiting time is something like 45 days. But of course, apply as early as possible.