While goofing around today on my lunch break, purely by accident I came across the website for digitized newspapers for New Zealand called Papers Past, put together by the National Library of New Zealand.
According to their Intro page, Papers Past contains more than one million pages of digitised New Zealand newspapers and periodicals. The collection covers the years 1839 to 1932 and includes 52 publications from all regions of New Zealand. What's even better, from what I can see, it is completly free!
If you have ancestors hailing from New Zealand, this might be a great place to look.