You can find a list of recrutment agencies (chasseurs de tête) on the SYNTEC Recrutement website : http://www.syntec-recrutement.org
If you are an experienced candidate with a good CV, I am sure it is worth contacting agencies.
If you are a junior candidate, I agree with Twig : you'd better contact companies directly. Take advantage of social networks like LinkedIn and Viadeo. I have always gathered useful information using these networks.
A selection of job boards : monster, cadremploi.fr, cadreonline.fr, apec, top-consultant.com (there is a French section!!!)
You will certainly need a French version of your CV. And be ready to introduce yourself in French on the phone. As you may know it, a lot of people at reception desks don't speak English and may hang up on you!
Hope it helps - Bonne chance !