Generally, places where it is forbidden there is good signage, or it is a place where it is not surprising to be forbidden.
Generally, it seemed that random stretches of highway would be posted, but just a mile or two down the road would be a spectacular place to pull over and hang out.
Additionally, many parks have areas in which camping is prohibited or restricted, but there would invariably be plenty of other places in which to camp, so it was never a big surprise. The NZ Dept. of Conservation website has a pretty good listing of where camping is prohibited or restricted. Many of the popular areas mandate staying at the huts, others are pretty relaxed, the DoC site will indicate which is which.
Overall, New Zealand is a pretty awesome place and if you just freestyle it, plan on free-camping but do no detailed planning, you won't have any problems. Rent one of those campervans or RVs and you'll have a blast.