There are a number of ways they could be doing this:
1. Tapping Internet traffic, either on peered networks or at an NZ ISP.
2. Placing spyware on individual computers,
3. Obtaining details of searches from Google and others.
4. Placing spoof sites and possibly paid advertising on search engines and then monitoring where the hits come from.
5. They're bluffing.
1 & 2 are plain illegal - section 216B of the Crimes Act prohibits the interception of private communications (which a search request clearly is).
4 wouldn't be illegal, but possibly also wouldn't be effective. They'd probably get a lot of hits on "lord of the rings torrent" - but that wouldn't be proof of anything. My guess is that this is the most likely methodology, apart from (5).
It will be interesting to see if any more emerges on this.