I seem to hear the same kinds of questions asked over and over again. I recently replied to a thread on JoelOnSoftware about how/when to work with recruiters. I figured it was worth repeating here.
DISCLAIMER: What follows is my opinion. My experience is in the continental United States, and I assume you are pursuing a full-time, on-site employee role. I suggest working with a recruiter if you can find one of high enough calibre, but that should not be your job search alone. Larger companies tend to work with candidates directly, as will small ones; it's the medium-sized companies that tend to use recruiters - in my experience.
That said ...
My advice is that if you are in one specific geographic area, very carefully pick a single recruiter and work with them. The reason to do this is because if you are working with four recruiters, and each sends your resume to BigCo, BigCo may decline to hire you for legal reasons. (They want to avoid paying four recruiters fees, and they want to avoid a lawsuit - or, more likely, strained relations and a lot of wasted time.)
Recruiters from large, publicly-traded companies (K-Force) tend to be more respectable. Recruiters that show up to user's group meeting s and don't get laughed at or "Called out" can be especially good. Ask who in that user's group, that they know, have they placed. Use that as a reference.
Groups that do permanent placement are usually better than contracting houses.
If you are thinking of moving, sure, work with one recruiter from NYC and one from California and one from Florida.
Conclusion: Get references, shop around, and pick ONE.
Schedule and Events
March 26-29, 2012, Software Test Professionals Conference, New Orleans
July, 14-15, 2012 - Test Coach Camp, San Jose, California
July, 16-18, 2012 - Conference for the Association for Software Testing (CAST 2012), San Jose, California
August 2012+ - At Liberty; available. Contact me by email: Matt.Heusser@gmail.com