Hello.
He can try to apply for jobs in hopes of being sponsored by an employer. But it is very difficult to be sponsored nowadays unless your husband has a specific experience and skills that a company is looking for. Most likely what will happen is your husband will not hear any response or be told, you need to have a visa to authorize him to work in Australia.
You had mentioned that the both of you are starting your application May 31, 2012. Has your husband's skills been assessed by the authorizing organization? Example if he is an engineer, he has to have his skills assessed by Engineers Australia. Before that, have both of you looked if he has enough points to qualify for visa 175 (indepedent)/176 (state sponsored ?
From the sounds of it, I don't think the both of you have met with an agency yet? I applied on my own for the visa 175 and was later granted. First thing that needs to be done is to see if your husband's occupation is listed in the SOL found in immi.gov.au If it isn't on there, I don't think he could apply for a specific visa. But if it is in there, then he needs to check if he has enough points to qualify. I believe it is 65 points in the current program. When I applied it was set up differently and we had to have 120 points. If he falls short of 65 points, I think they state the application will be rejected since there are other applicants meeting the points requirement.
In case your agency doesn't mention it, the skilled migration program will be changing this upcoming July. It is called Skilled Select and people are stating it will be more competitive. You submit an Expression of Interest (EOI) with all information being asked. Then only if you are invited to the Department of Immigration & Citizenship (DIAC) can an applicant be apply. The applicant's information is in the database to what I believe is for 2 years. This is a different set up compared to now that you can apply for the specific visa and for the DIAC to determine if you meet the qualifications and will grant you.
It takes about 3-4 weeks or more depending which occupation your husband's organization falls under to be assessed. I am not sure if the both of you can get all your paperwork ready before you can apply all before July 1. Your husband will need that letter confirming that his skills are recognized in Australia before you can even submit an application. Then there is also IELTS (english proficiency test) that both of you may need to take? Countries that are English speaking like US, Canada, UK,etc. don't need to take this test. However, if an applicant needs additional points, they can take this IELTS to increase their total points if they reach a certain level band.
I would highly recommend that the both of you visit immi.gov.au and read about the different type of visas available. Also, to read more about the Skill Select Immigration Program before you see your agency. At least you will be able to ask more questions.
Just a note that using an agency doesn't necessarily mean you have a better chance than someone that applies on their own. You just need to make sure you have all the documents the DIAC is requiring,etc.
Lastly, some online job websites for your husband to look at are mycareer.com.au or seek.com.au
Good luck.