1) As educated white people, you'll be fine. Specifically, your wife will want to apply for a student visa once she's accepted into a PhD program. My understanding is that it's basically a rubber stamp if you're on "Assessment level 1" - which you get automatically by being from the USA. The family all get to live and work in Australia on that visa (only once she's started studying) and you can work full-time if she's postgraduate (see here: http://www.immi.gov.au/students/_pdf/permission-to-work-stud...)
There's a lot more information here: http://www.immi.gov.au/students/
Once she's finished, you'll need to switch to another visa to become a permanent resident, probably this one: http://www.immi.gov.au/skilled/general-skilled-migration/885...
2) I'm not sure where you heard that, but to my knowledge PhDs here are the same as elsewhere. Becoming a lecturer generally requires a PhD, which is a degree attained through high-level research under an advisor, requiring a masters or honours degree.
You may be thinking of masters by research/masters by coursework, which have the distinctions you're talking about (although with masters by research you still have an advisor). There are also graduate certificates and diplomas, which are basically the short-course equivalent of masters degrees. You can read more on Wikipedia: http://en.wikipedia.org/wiki/Australian_Qualifications_Frame...
3) Our three main general job sites are monster.com.au, seek.com.au, and mycareer.com.au - they suffer from (I imagine) the same problems big job sites would in other countries, which is to say they're full of recruiters and have a low SNR.
If you're looking for something in tech, you're often better contacting the source directly. Most Australian tech companies have a standing we're-hiring-just-send-us-a-resume policy. For example:
http://www.atlassian.com/about/careers/
http://www.google.com.au/intl/en/jobs/
http://careers.microsoft.com/careers/en/au/home.aspx
Alternatively, if you're looking for startup work there's a quite active mailing list called Silicon Beach: http://groups.google.com/group/silicon-beach-australia
And a specific silicon-beach-jobs list (set up only recently): http://groups.google.com/group/silicon-beach-jobs
Hope that helps!