Their navigation skills took them to the Solomon Islands, around 1600 BC, and later to Fiji and Tonga. 
By the beginning of the 1st millennium BC, most of Polynesia was a loose web of thriving cultures who settled on the islands' coasts and lived off the sea. 
By 500 BC Micronesia was completely colonized.

2003 B.C.   A Piece of Wood 
Recreational wave riding , either body surfing or assisted by a small board, was practised throughout the
Pacific Islands and probably predates the Polynesian migration from Asia, which began aroudnd 2000 B.C. 

Whatever it's primitive origins, by 400 A.D. when the first settlers reached Hawaii, five principles had been
firmly established... 
1. wave riding is fun - the thrill of the ride in is greater than the effort of the paddle out. 
2. wave riding can be dangerous 
3. the surfer must paddle in the same direction as the wave to achieve take-off. 
4. the ride is longer and faster if the surfer rides diagonally across the wave face. 
5. a rigid board will improve  planning and paddling - but can also increase the danger factor. 

A  small wooden prone board used thoughout  the Pacific Islands, primarily as juvenile sport. In Tahiti and
Hawaii the boards were ridden prone, kneeling and, occassionally, standing. Other Pacific Islands were
restricted to prone riding only. 

The origin of these boards is speculative, but broken sections from discarded canoes, outrigger floats or
paddles (the blades) are  possible sources. Dimensions ranged from 3 feet x 12 inches (the smallest example
in the Bishop Museum, Honolulu. Catalogue Number :C.5966) to 6 feet x 9 inch boards in Aotearoa (New
Zealand). 

With the development of an adult surfing culture, prone boards  became essential in acquiring basic surf skills.

Pre- Hawaii - Conjecture.
Exodus from Asia about....
Initial migration by small groups across small distances in crude craft.
Travell would be directed at observable land masses, that is approximately 5 kilometres.
Craft could vary from a simple single log to a timber raft. 

As distances between islands became longer, larger rafts would be required to carry larger numbers of passengers and or supplies.
On occassion rafts could possibly be wind driven by a simple square sail.

The development from this crude base to sophisticated sailing canoes was concurrent with the use of a simple board for personal transport over short distances.
The use of a small paddleboard  was to have two significant impacts on Polynesian culture....

1. It was adapted as a tool of recreation (exhilaration?) with the development of surfriding.

2. Originally a floatation devise, board paddling became the basis for Polynesian swimming, incorporating an overarm stroke of the arms and a sissor-like kick by the legs.

At the start of the 20th century, the Polynesian style (often mis-labeled the Australian Crawl) was becoming the dominant competitive swimming stroke. 
It was emphatically demonstrated by Duke Kahanamoku's 1908 Stockholm Olympic performance.

By the end of the 20th century surfing had spread to across the world's oceans (and Lakes!) and surfing culture had global significance

Hawaii
The Polynesians arrived in Hawaii circa 1000 B.C. with an unequalled maritime knowledge and skills to the finest surfing location on the planet. 
Not only was there consistant swell and a tropical climate, but a previously untapped store of timber. Unihabited for X0000 million years, the Hawiian Islands had produced a massive store of surfboard building materials - trees large enough to build sixty foot canoes

The main timbers were...
Willi Willi (Erythrina sandwicenis) - a light timber similar to balsa wood and used for outrigger floats.
Breadfruit or Ulu (Artocarpus altila) - also light
Koa.(Accacia koa) -a fine grained hardwood.
Some reports suggest that Breadfruit or Wilii Willi were preferred timbers (particually for the longer Olo) for their lightness (and ease of shaping?), however the only  existing examples of these boards are in Koa wood.  Probably the lightweight nature of these timbers was the cause of their disappearance.
Some small (Paipo) examples exist in Breadfruit.

A tree was selected and felled, sometimes with religous ceremony or offerings, and a board was roughly shaped by a stone adze on site. 
The board was then moved to a Canoehouse or beach site where the shape was completed progressively with adze, various coral heads and an oahi rubbing stone. 
Several staining  agents were availaible...
Root of theTi plant (Mole ki)
Juice of pounded Kukui bark
Soot of burnt kukui nuts
Charcoal from burnt pandanus leaves
Juice from banana buds
Ashes of burnt cane leaves
Usually several agents were mixed to produce a glossy black finish. 
One account quoted by  Tom Blake states that a willi willi board was immersed in mud to seal the timber grain (page 45).

The finishing process was completed with the addition of kukui nut or coconut oil to assist waterproofing. These contruction processes were not exclusive to surfboards - they were standard practice in canoe building.

Further coatings of oil were regularly applied as ongoing maintainence.
After use boards were dried and stored, sometimes wrapped in cloth.

Dimensions vary between 6 feet and 12 feet in length, average 18 inches in width, and  between half an inch and an inch and a half thick. 
The nose is round and turned up, the tail square. 
The deck and the bottom are convex,  tapering to thin rounded rails.
This cross-section would maintain maximum strength along the centre of the board and the rounded bottom gave directional stability, a crucial factor as the boards did not have fins.

Alaia and Surfer, Waikiki 1890 (Bishop Museum) Kampion, Page 29	Surfers and Alaia, Hilo Bay, Hawai'i circa 1900 (Bishop Museum)  Cropped from Lueras, page 56 and 57

Any discussion of the performance capabilities is largely speculation. 
Contemporary accounts definitely confirm that Alaia were ridden prone, kneeling and standing; and that the riders cut diagonally across the wave. 
Details of wave size, wave shape, stance and/or manouvres are, as would be expected, overlooked by most non-surfing observers. 
Most early illustrations of surfing simply fail to represent any understanding of the mechanics of wave riding. Modern surfing experience would suggest that high performance surfing is limited more by skill than equipment.
It is a distinct probablity that ancient surfers rode large hollow waves deep in the curl - certainly prone, and on occassions standing.

Standing Rider on Paipo/Belly board,  Kuhio Pier, Waikiki, circa 1962 Photograph by Val Valentine Kelly, facing page 192.

By 1000 A.D these principles were confirmed...
13. Large waves are faster than small waves.-  a larger board is easier to achieve take off.
14. Steep waves are faster than flat waves.- a smaller board is easier to control at take off.
15. Control is more important than speed
16. Surfboards are precious.