Even if your ISP does not give out native IPv6 (by the way, it might be a good idea to ask), you can make the IPv6 tunnel with decent performance over IPv4.
To do so, you need to get a tunnel from one of the tunnel brokers. There are two tunnel brokers that offer free IPv6 tunnels:
Both tunnel brokers support the dynamic endpoints although the update algorithms are different. The Hurricane Electric update involves just a predefined HTTPS request, while the SixXS uses a more secure algorithm, described in this expired IETF draft.
Also, SixXS has a "point system", where the user mistakes are "punished" by taking out "credits" - so an intensive RTFM is highly recommended before messing around. However, if one uses the supplied "aiccu" package, the setup should be relatively straightforward. And, as well, there is plenty of material to RTFM. This link, for example, gives a good overview of how to configure your device to work with the service.
Kudos to both of the parties for the excellent service they provide to the community. Also - both of them provide the recursive DNS servers, that are serving the Google's AAAA records - so you can watch YouTube over IPv6.
If you, like the author of the page, would just like a small VPS, then I can recomment going with RapidXen. For a very reasonable amount per month you can get yourself a Xen-based VPS with IPv4 and native IPv6 connectivity. And the folks hang out on IRC. Just wait and do not rush asking "when my machine is going to be ready?" - it takes 1-2 days for provisioning.
Of course, this is only personal experience, but at the moment there are surprisingly few offerings with IPv6 for VPS. You can read more here, there are a few more providers you might try.
Disclaimer: I am in no way associated with the entities that I mention above, nor getting any benefit from their "advertising" here - just sharing the experinence.
Matthew Walster says: Very impressed with FOSDEM IPv6 connectivity, RAs seem to be working, just plug in and play, as it should be! Well done!