http://www.teara.govt.nz/ is the new electronic encyclopedia for New Zeland... and it's got a great section on native cephalopods here: Octopus and squid
According to legend, the Polynesian navigator Kupe was led to New Zealand by the giant octopus Te Wheke-o-Muturangi. Intent on killing the octopus that was robbing his tribe of fish, Kupe, along with his family and some warriors, set out in a large canoe to hunt it down. The octopus swam south for weeks and eventually took shelter near Cook Strait, where Kupe found it. After a ferocious battle, Kupe tricked the octopus into wrapping its arms around some water containers, and killed it with a blow to the head.
Māori caught octopus by hand. They placed one hand into the water to act as bait and when an octopus wrapped its tentacles around their arm, they seized the body with their other hand and hauled the animal out of the water.