Recruiters have varied reputations – I'd say there's no harm in contacting one, but I wouldn't count on it as my sole bet.
My biggest piece of advice for anyone starting the job-hunt is to get signed up for emails from the job-search sites – careerbuilder.com, monster.com, indeed.com, etc. Get email alerts for anything with “CPA” in the job description or “Accounting” or whatever search term(s) you think would be best, and get them sent daily for the area you're looking in. This way, you'll never be the last person to hear about the job posting. Definitely sign up with multiple sites, too – it might show up on Indeed today, CB Monday, and Monster next Wednesday. If they're in a hurry, they might already be doing interviews from the folks who saw it on Indeed before you see it through Monster, if Monster was the only one you were signed up with. Or it could start on Monster and go the other direction. I'd also sign up with usajobs.gov and your state website, if you're interested in government work.
Beyond that, if you're looking to work in public accounting and interested in small firms, I'd suggest going door-to-door visiting the small local firms and dropping off a resume and cover letter. That's how I got my first accounting job, in tax accounting. My next job in private I got through email alerts and my current job in private I got through watching the website of my employer, since I knew they rarely post their jobs to any of the job search sites.
Whatever route you go, though, a polished resume and cover letter are essential. Enlist the help of anyone you know (probably except people you currently work with) that can help review and advise to make it as good as possible.