I have a Xilinx Spartan-3 dev board, they cost around $100 including JTAG and power supply (
http://www.digilentinc.com/info/S3Board.cfm). Why Xilinx? Because thats what we use at school, so I was forced to buy that board for a class. Plus its probably one of the best known FPGA and CPLD companies. The Xilinx ISE webpack is free, and theres a free limited version of modelsim for it too (but still provides basic simulation stuff). The xilinx software does leave something to be desired though, as its not the most stable software (although 7 seems to give me fewer problems than 6 did). Just make sure you save often.
The easiest way to start is to just design in schematic form, but this quickly becomes more work than just using a hardware description language. I'm not too familiar with AHDL (I think its Altera's version of VHDL), as we use VHDL at school and Verilog at work. VHDL or Verilog are probably better, as they are more standard instead of specific to one company's products. I suppose if you wanted to do it on the cheap, you can just grab ISE and modelsim and start using it, and just see the simulation values you get. Eventually you will want a real device to play with though.