It depends on the dates you are looking for, and also which state, each of which has different records and availability. So levels of access depend on where they landed, or ended up living. There are more passenger indexes for the 1800s than for the 1900s, and I know only about two of the states - Victoria and NSW - which had the majority of immigrants arriving in the 1800s. Some Queensland ones are included in NSW records.

NSW has good indexes to arrivals of convicts and assisted immigrants, and excellent free indexes to BDMs - you then can buy the certs online. The certs are very informative, giving ages, where born, details of how long in the country, both parents' names, children's ages, details of spouse, addresses, etc.
http://www.records.nsw.gov.au/archives/indexes_online_3357.asp
and:
http://www.bdm.nsw.gov.au/familyHistory/search.htm

There are good online indexes for passengers to Victoria, and there are also Vic. BDMs online, but for a fee.
http://online.justice.vic.gov.au/servlet/bdm_home
Sorry, the passenger indexes are down at the moment, but I think this is the right URL [will check tomorrow and repost if wrong]:
http://proarchives.imagineering.com.au/index_search.asp?searchid=23

For national records after about 1920 see: http://naa12.naa.gov.au/scripts/ResearcherScreen.asp

Sue