Some places that are looking to hire have already signed an agreement with a particular headhunter which you'll have to then use, but in many cases, the ED director is looking passively and not signed anyone. If you cold call them and hit them at this time, things can work out great for you. The downside of signing with a headhunter is that anyone who hires you owes them a significant finder's fee... often $10-20k. This can be a significant downside for a director who can choose between you and your headhunter (and losing an extra $20k to hire you) or someone unaffiliated whom he does not have to pay a finder's fee. Given that they don't really do anything that you can't do with a little elbow grease and effort, you should consider just working by geographic area.
Headhunters have a job to do and a business to run, but don't sign anything until you've asked your program director's advice and thought things through. They're like vampires: they can't come in until invited, but once invited are with you forever.