National Library of Australia has announced that as of the 3rd of August 2010, there are 2,197,113 pages consisting of 23,128,582 articles available to search.
This site has been going since July 2008 and relies on you and me to correct scanned text so that it is easier to search. I've done a few columns myself - have you? They say the public have corrected 12.5 million lines of newspaper text so far. So if you have some spare time and like history, you won't be bored by it.
They hope to complete their program by the middle of next year.(1800's to mid 1950's). I've found a lot of early passengers to New Zealand before the 1840's and do searches for people who have come through Australia to New Zealand with success.
Because the text has not been fully corrected yet, it pays to be creative with your search keywords.