As long as most providers do not provide direct IPv6 connectivity the most common solution will be to tunnel IPv6 traffic through the IPv4 network to some site that is IPv6 connected. Sites that allow others to use them for IPv6 connectivity are called tunnel brokers.
Most commonly the 6in4 protocol is used to tunnel IPv6 traffic through the IPv4 Internet. Each tunnel consists of two end-points - one at the client side (usually the local gateway to the Internet) and one at the tunnel providers side (tunnel server) - while the networks behind both points are normal IPv6 the network between them (in IPv6 terms called 'gap') uses IPv4 only.
In this protocol each IPv6 packet is encapsulated in an IPv4 packet by simply prepending it with an IPv4 header in which the protocol number reads 41 (TCP would have 6 and UDP would have 17) - on the other side of the tunnel the IPv4 header is stripped away and the IPv6 packet can continue on its way in the native IPv6 network.
The 6in4 protocol has the drawback that it does not work over NAT - unless the NAT gateway is configured to forward the protocol 41 packets to a specific host inside the NAT network. Unfortunately most off-the-shelf NAT routers support port forwarding at best, and almost never protocol forwarding.
If you have a static IPv4 address for your router or want to try out IPv6 only for a few hours, then the public 6to4 gateway network is probably the way to go for you.
The 6to4 network consists of a number of tunnel gateways that are spread internationally. Each node is reachable under the IPv4 anycast address 22.214.171.124. The local network will get a /48 prefix that consists of 2002::/16 plus the 32bit static IP address in hexadecimal notation (eg. 126.96.36.199 becomes the gateway to the network 2002:0102:0304::/48). The embedded IPv4 address is used to route the tunnel traffic.
You can structure your /48 network however you like internally.
A good Linux tutorial for setting up 6to4 can be found at TLDP.
If you have changing IPv4 addresses or are behind NAT, but have an (almost) always on connection, then SixXS is a possible solution. SixXS uses two different modes of 6in4 and a protocol called AYIYA to tunnel traffic. While 6in4 requires either direct access to the router or protocol forwarding, AYIYA can cope with NAT (at least if UDP is routed over it).
In their own words: "SixXS (Six Access) is a free, non-profit, non-cost service for Local Internet Registries (LIR's) and endusers. The main target is to create a common portal to help company engineers find their way with IPv6 networks deploying IPv6 to their customers in a rapid and controllable fashion."
From it not being for profit follows that requests are handled when someone has some spare time at his hands and that you need to tell them what your motivation for requesting a tunnel is - it is up to the SixXS staff to acknowledge or deny your requests.
The steps for connecting to SixXS are quite simple:
A little hint as for the SixXS homepage: the sixxs.net domain has DNS records for IPv4 and IPv6, so depending on what browser you use and whether IPv6 is already enabled in your system it may happen that the browser times out although SixXS would be available over IPv4 (so seen with older versions of Konqueror), try a different browser (Firefox 3.x worked for me) or disable IPv6 entirely for the moment.
The Teredo Tunneling Protocol connects a single host to the IPv6 network. Like 6to4 it uses a network of different gateways to relay traffic, but unlike 6to4 it uses UDP and is capable of traversing most NAT routers. It is very useful to connect a single node to IPv6 in an otherwise very restricted environment if no other more reliable tunnels are available, but it has several drawbacks:
But on the upside: it is very easy to use - Windows XP SP2 and Vista have it already turned on, for Linux and some other Unixes there is Miredo (which usually comes preconfigured, you just need to install it).
There is a number of commercial and free tunnel brokers. See for example Wikipedias List of Tunnel Brokers. Most of them will use the 6in4 protocol, some will use other protocols - configuration details can be found at their home pages - other than with traditional services Linux How-Tos are usually easily accessible.