Sadly, even if an agency may be a licensed organization, their quality of services may be poor and attitude toward foreign workers hurtful. The following is a link to a lot of agencies in Canada who may or may not be licensed. (Please refer to BCGuy's suggestions as to how to verify whether an agency is licensed or not.)
http://www.jobagencies.ca/index.asp?p=1&sp=1The link also gives links to individual agencies where you can find general information about each agency and people's experience with, or remarks about, that agency. An average rating on a scale of 1 to 10 is also available.
I traversed over remarks, a lot of which are about how agencies treat prospective foreign workers rudely (i.e. rude over the phone, not answering emails, asking for money, advertising non-existent jobs just to hunt CV's, etc etc)
I even personally spent some time on a licensed agency that prepared an entire webpage for foreign workers with a well-formulated procedure on how to get hired by a Canadian company through them. The page contains a stringent set of steps. Throughout the page they warn that if any step is missed they will cancel the process and give it to someone else! They even say, "If you don't timely answer our mails we will assume you are not interested and we will cancel processing your case." It felt quite slippery. Some lines about getting LMO without even sending a CV to an employer seemed suspicious. So, I emailed them questioning those lines and got no replies. What an irony it was! They expect quick mails yet they don't answer mails themselves! They are off my list.
In conclusion, I think getting a job through an agency in Canada could be quite risky, even though it might be the best way one could get through to an employer.