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
I haven't tried it, as I have a much cheaper but far less documented CPLD sitting around, gathering dust. =p
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 would love to put together a softcore Lisp Machine. It would a tremendous learning experience and I think it could help spur some really interesting results in OS architecture. Particularly useful in that arena would be a multicore Lisp Machine.
It would be a dream come true if I got a job building such a device and development was open-sourced from day 0.
[1] Softcore, that is, a processor on an FPGA.
http://zslug.wordpress.com/2011/02/09/meeting-1-report-audio...
i had a few of the 3600 lisp machines, they wouldn't be hard to fit into a fpga at all (size wise, of course :). they had huge boards filled with chips, which were all... hand wirewrapped cmos chips (iirc) .