To learn how FPGAs work, I'd recommend starting with a cheap Digilent board; see http://www.digilentinc.com/choosing.cfm - You can get a simple BASYS 2 board for under $100, possibly under $50. This board is the Arduino of the FPGA world. There are tutorials from many schools, lots of good documentation, it's a proven design...you can't go wrong with the Basys board. It does sacrifice performance for simplicity, though - Notably, there's no RAM except for what's on the FPGA. Go up to the Nexys for that, but if you're just interested in learning Verilog/VHDL, the Basys is a fine place to start.

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)

I had pretty decent success with the products from KNJN (http://www.knjn.com/). It's affiliated with FPGA4Fun (http://www.fpga4fun.com/) which will help with the learning.

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.

If you're new to FPGAs or digital design in general, it'd probably be worth your while to pick up a good digital design book. I always liked Wakerly's Digital Design Principles and Practices. I recall that my edition (either 2nd or 3rd) was VHDL-focused, but it looks like the 4th edition has examples in both VHDL and Verilog.

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...

My interest with FPGAs is more designing processors rather than interfacing with electronics. I like the products from OpalKelly [http://www.opalkelly.com/] for this as they have a USB interface and C libraries on the computer side, HDL on the FPGA side to abstract the host->FPGA communication allowing you to just focus on your design.

Adafruit has an FPGA for sale: http://www.adafruit.com/category/products/451

I haven't tried it, as I have a much cheaper but far less documented CPLD sitting around, gathering dust. =p

I haven't tried this particular development board but it looks pretty inexpensive and would be a good starter board. http://www.easyfpga.com/

I've heard good things about the Papilio: http://papilio.cc/