And don't forget the National Archives for records (mainly) from 1900 onwards - of immigration, naturalisation, war records (full scans for WW1), etc. www.naa.gov.au/collection/recordsearch/index.aspx
Use "Search now" as a guest.

Another good website which tells you exactly what are on b/m/d certs in all states by date:
www.jaunay.com/bdm.html

Sue