The Polynesians used pandanus leaves. It is really interesting what did the Maori use, because I'm not sure that pandanus could thrive in relatively cold New Zealand (there are some 600 species of these plants, but almost all of them grow in the tropical zone of Earth). In OTL the Maori cultivated New Zealand flax (two species - harakeke, wharariki) for their clothing, baskets, nets and so on. This website (http://www.alibrown.co.nz/history-of-new-zealand-flax.html) claims that New Zealand flax is ideal for sail-making too, but there is no examples of Maorian sails on the site. Maybe, the Maori discontinued long-distance maritime travel because of want of pandanus and (possible) unreliability of New Zealand flax as material for sails?