To learn how these things work, get a job at a company which uses FPGAs. You'll probably never see one of these parts as a hobbyist.
If you're interested in stuff that's actually like this, and want to start right away, then look for a board packaged as a PCIe card. This will be significantly more expensive; think $500 on the extreme low end. NetFPGA is (http://netfpga.org/) is a good starting point if you're trying to start at a higher level. (Note that the old board is 33MHz PCI and the processor is obsolete; you want the 4x10GBE Virtex 5 part if you're looking for modern tools)
The founder of the company is a pretty spiffy speaker as well; if you have a chance to see him, it's worth it.
Recently I've been looking at the small, low-cost boards by XESS - http://xess.com/prods/prod048.php
Keep in mind that writing logic is quite different from programming. It's quite the mind-shift.
There's also the matter of working through the FPGA toolchains, which isn't exactly a walk in the park. Unfortunately I don't have a good tutorial to reference off the top of my head...
I haven't tried it, as I have a much cheaper but far less documented CPLD sitting around, gathering dust. =p
Some of them use external CPUs, but newer generation ones such as the FPGA Arcade can hold pretty much the entire machine include the CPU in the FPGA (usual exception is RAM, and a micro controller to bootstrap).
See FPGA Arcade, Natami, Minimig, C-One, Chameleon and others. Natami is the most capable of the bunch (aiming to be a faster, better Amiga), while Chameleon is probably the smallest (the size of an old style Commodore 64 cartridge, and can plug into a real Commodore 64, since it started as a C64 expansion on steroids, but it can run standalone too), with FPGA Arcade a nice middle group (fits in Mini-ITX form factor boxes, but isn't deep enough to fill nearly all of the box).
FPGA Arcade: http://www.fpgaarcade.com/ Chameleon: http://www.vesalia.de/e_chameleon.htm