It appears New Zealand Maori actually introduced the haka to rugby (history), in their tour of Britain in 1888/89. Although this history story describes a somewhat vaguer origin (therefore more likely?) it also credits the ‘New Zealand Natives’ with the first overseas performance of the haka by a rugby team. Since 2001 NZ Maori performs the Timatanga haka which describes the evolution of life and the creation of New Zealand from the four winds. ps. The story of the All Blacks’ haka has a good entry on Wikipedia, and there is a separate story about the Kapa o Pango throat-slitting controversy.