It depends a certain amount on the island group under question and what we mean by permanent.
In Aotearoa (New Zealnd) the Maori were well known the Pa that they built; essentially wooden fortifications that may or may not have usually involved some earth works, but certainly did by the time Europeans came into armed conflict with the Maori. The Pa are often depicted in European paintings as being like a Greek Polis; whether or not that has any basis in fact; it certainly gives us some idea of how Europeans interpreted the Maori Pa.
In Hawaii as another poster mentioned, the Heiau or religious buildings were built with stone walls around them; some of them several stories tall. Many of the Heiau have been destroyed; their stones repurposed for newer construction projects (read bridges, churches, and houses). There are still many large Heiau that you can visit, including a pretty huge one Hikiau where Captain Cook stopped by for a visit and eventually never left. In Hawaii there are also fish ponds or various sizes (from a few acres to many acres); the fish ponds are giant stone structures that inclose the ocean- allowing water to flow in and out and the fish to stay in. Some of the fish ponds were truly massive and could feed tens of thousands of people with their produce. There was also an ancient highway built in Maui laid with river stones to facilitate movement around the island, but that no longer exists. Also there is a great deal of terracing that was done across the islands to increase the amount of productive agricultural space; some of it is still visible (especially in places like Kohola, Hawaii), but for the most part you will need to read about it in archeology monographs (like Anahulu by Patrick Kirch), as development has covered up much of what existed.
In Tahiti there are the Marae; very similar to the Heiau in Hawaii; thought some of them could be bigger and have great stone foundations; particularly impressive is the mare at Taputapuatea on Raiatea which was a major marae for Tu- the god of war and fertility that became ascendent in Tahiti a few hundred years before the arrival of Europeans. It is also a significant Marae for polynesian voyaging- even to this day- and the Polynesian Voyaging Society has staged several events there, and the Hawaiian wa'a Hokele'a and Hikianalia have both made stops there recently as part of their World Wide Voyage; so not only was Taputapuatea a significant (both in size and power) place, it remains so.. Tonga has the Ha'amonga 'a Maui, a huge stone gate that exists on Tongatapu.
Though /u/iwinagin mentioned Nan Madol on Pohnpei, that's not really in Polynesia (geographically or culturally); but its still impressive and to it we should probably add the Lelu complex on Kosrae to that which also features artificial islands and reclaimed land on a scale only slightly smaller than Nan Madol, though certainly less well known; though it is likely the two are connected historically, it is unclear precisely how. And we could also add the Latte stones from Guam and the Marianas which resemble stone pillars from 3-12 feet and were possibly used to support houses which could then sit higher off the ground and catch some breeze.
There are certainly others as well; these are just the ones I am familiar with off hand. I also wrote this assuming you meant megalithic structures and nothing too modern; after all there are quite a few large structures that have been built since ~1800 CE, but I assume you aren't looking for those!
edited to add sources noq that I'm not on a mobile
On Aotearoa and the Pa;
Smith, Bernard. European Vision and the South Pacific. Melbourne: Oxford University Press, 1989.
Salmond, Ann. Two Worlds: First Meetings Between Maori and Europeans, 1642-1772. Honolulu: University of Hawaiʻi Press, 1992.
On Hawaii; heiau, fishponds, terracing
Kirch, Patrick Vinton. On the Road of the Winds. Berkeley: University of California Press, 2002. (Also good general overview; discusses nearly all of this)
Kirch, Patrick Vinton and Jean-Louis Rallu, ed. The Growth and Collapse of Pacific Island Societies: Archeological and Demographic Perspectives. Honolulu: University of Hawaiʻi Press, 2007.
Kirch, Patrick Vinton. Anahulu: The Anthropology of History in the Kingdom of Hawaii (Honolulu: University of Hawaii Press).
Kirch, Patrick Vinton. Kua'aina Kahiko: Life and Land in Ancient Kahikinui, Maui (Honolulu: University of Hawaii Press, 2014). (haven't read this last one, just read a few chapters here and there, but seems promising- almost like a longue duree history of a french village in the early modern era, but done on settlement on Maui instead).
On Tahiti;
Finney, Ben. “The Sin at Awarua.” The Contemporary Pacific 11:1 (Spring, 1999): 1-33.
Dening, Greg. Mr. Blighʻs Bad Language: Passion, Power and Theatre on the Bounty. Cambridge: Cambridge Univeristy Press, 1992. (especially 'interlude' about consecration of Marea/construction and expansion- gives good sense of size and function)
Salmond, Ann. Aphroditeʻs Island: The European Discovery of Tahiti. Berkeley: University of California Press, 2010.
On Micronesia (while not geographically Polynesia - if we even accept these terms to mean anything- still very impressive megalithic structures)
Rainbird, Paul. The Archeology of Micronesia. New York: Cambridge University Press, 2004.
Hezel, Francis X. First Taint of Civilization: A History of the Caroline and Marshall Islands, 1521-1885. Honolulu: University of Hawaii Press, 1983.
Since /u/b1uepenguin gave you a nice overview of Polynesia, I thought I'd zoom in and deal with one island in particular. While the moai are the most famous of Rapa Nui's constructions, they're by no means alone. To begin with, there's the ahu, which are architectural cousins of Hawaii's heiau and Tahiti's marea. With the exception of the road moai and a few others (speaking of which, the Moai Roads radiating from Rano Raraku also count as permanent constructions), most of the moai are found on the ahu near the coast. However, since the ahu usually predate the moai, they were enlarged and upgraded when the moai were installed. For example, the Ahu Tahai, near Hanga Roa, is the oldest known ahu, dating back to around 700 CE if not earlier. But the original ahu has since been buried under the nearly 2000 tons of stone used to construct the upgraded ahu several centuries later.
The original houses on Rapa Nui were long, low structures resembling overturned canoes called hare vaka. The cobblestones outside the house in that reconstruction indicates that its an elite residence, or to be more specific, an elite residence at the time of sustained European contact. Earlier elite houses, the tupa, were built entirely of stone. As in the ruins shown here, the tupa often have watchtowers associated with them. In addition to the typical defensive use of watchtowers, these structures provided elevated observatories for astronomically-minded tohunga and places to watch for sea turtles coming ashore. The best preserved / reconstructed tupa are at Orongo, an important ceremonial site on the island. Originally it was the site where rites of passage into adulthood were conducted, but by the time of sustained European contact, it had become integrated into the relatively new Tangata Manu ceremonies, which persisted into the latter half of the 1800s.
The Rapanui also built ringed gardens known as manavai. These protected their crops from wind erosion, retained moisture, and fertilized the soil as the volcanic stones chemically eroded. The Rapanui also employed this sort of "lithic mulching" in unsheltered fields by scattering volcanic stones among their crops. By the late 900s CE, there's also evidence that the Rapanui had begun establishing palm plantations (not permanent standing structures in the usual sense, but definitely representing long-term efforts). Unfortunately it seems the koire problem wasn't solved int time to save the palms.
Sources
