Don't try and give your client machines IP addresses -- make use of the stateless address auto-configuration and just set up zebra or radvd on your gateway. See Simple IPv6 HOWTO for a quick introduction.
The following Tunnel Brokers are well known for the New Zealand area, see the Wikipedia link for more information about them:
SixXS also allows manual configuration though, eg with static tunnels. Manual configuration is partially possible with Hexago's Gateway6.
If you want a statically assigned address, you'll probably need to use a tunnel broker, which is most likely, latency wise etc, a good idea anyhow. Otherwise you can try 6to4 or Teredo though latency for those and debugging is far from optimal, they also don't provide static addresses.
For debugging, you'll want to install traceroute6 and ping6; on Debian, apt-get install iputils-tracepath iputils-ping.
A cheap way of installing IPv6 under Linux is to grab a 6to4 script, put it in your /etc/init.d directory, and set it to run on boot. That's it, you're done. (See 6to4 for a more involved explanation as to what this script does.)
Start up a command prompt and type netsh int ipv6 install
The following page may be of some assistance: Microsoft IPv6 Technology Preview for Windows 2000 Downloads with fixes for various services packs can be found here
There is a beta stack available, it works, but try to avoid this platform, it is old.
GENERIC supports it by default, but otherwise compile support into your kernel with the following options
options INET6 device gif # IPv6 and IPv4 tunneling device faith # for IPv6 and IPv4 translation device stf # 6to4 IPv6 over IPv4 encapsulation