The BDM's for each state can be accessed up to varying cut off dates (privacy laws) and passenger lists of various coverage are also available from each state.
The National archives have inwards passengers from early last century from not too long after Federation.
Convict records are available from the New South Wales, Tamania. Western Australia and Queensland Archives
One thing that the convict system did was create fairly extensive and detailed archives right from the beginning in 1788.
Cheers
Peter
Melbourne