As far as 'host software' goes, Altera, Xilinx, Lattice, Atmel, and Actel all provide licensed 'free' software for downloads. of course not all the features can be used, like IP cores, but for getting started its more than enough. 50K gates designs can be made using them.
But be warned, generally the software download is between 500-800MB. License is available on request.
Hardware, the chips are pretty cheap, and dev systems from china are very reasonable. Just check ebay.
As far as 'programming/configuration' goes, this is where I tihnk the FPGA/CPLD manufacurers let the 'beginers' down. Generally theres a parallel port version (and not all of us have native LPT ports on our PC's anymore), or a USB version, which, altera's 'USB blaster' is around $150, but xzilinx's is around $300. - Ridiculous.
So, if I were you, I would get a LPT PCI card if you do'nt already have one...or...design you're own JTAG programmer software.
One caveat with altera devices. If you use CPLD's with built in memory (not FPGA's which use external config) then Altera's devices are rated for 100 erase/programming cycles minimum. Sounds like a lot, but I have already bricked 3 devices by going over this. MAXII devices, which are like small to medium FPGA's, but with built in Flash, osc etc.. are like this too, which is a pity as they are cheap, huge (1900 registers?) and there are many cheap kits for them.
I'd go with either xilinx or Altera, since almost all resources on the internet are designed for those.
Best place to go to is:
fpga4fun.com - Welcome
There was a webshop there with fantastic little boards to get you started. FUll of examples and software for example projects.
Blueteeth