Being nervous is a big part of the whole relocation business. Personally I would steer clear of recruitment agencies. They're great for say the nursing/medical profession, but for normal 'every day' jobs, I've not heard any good reports. If you're good at your job, have all the necessary paperwork to prove it, then you shouldn't have much trouble getting a job on your own merit. I'd pay them money as a last resort, not first!
I think you'd be better to apply for jobs when you arrive, as most employers like to conduct interviews face to face. All part of the deciding factor