I think there's two questions implicit here, firstly "did the Polynesians know about Australia" and secondly "did maritime Southeast Asia know about Australia?" The Maori of NZ are distantly related to the Malays, but only very distantly. Any Malays proper in New Zealand got there after colonisation.

Previous answer on the former (n.b. that the AH backlog on this subject seems pretty speculative, so newer answers would be great):

/u/b1uepenguin on lack of Polynesian migration to Australia

/u/anangrypacifist on general notes about exploration of Australia

Previous answers on the latter:

/u/mikedash on possible pre-European contacts between Makassar and Arnhem Land

/u/wotanweevil on the same

/u/pangerandipanagara on trepanging in Arnhem Land