I'm using Altera tools for work right now. We have a paid seat, but even in free mode, the web kit is powerful enough to do pretty complex stuff. To experiment with the software, go to altera.com, click download in the upper right corner and download the web kit.
Unfortunately, the linux version is not free but you can use it for 30 days without a license.
Xilinx also has a free version you can use.
As for development boards, here's the cheapest FPGA board I found for Altera: http://www.altera.com/products/devkits/altera/kit-cyc2-2C20N.html
I'm using the Cyclone III version of that board. Its quite good.
For a Cyclone I board, these look inexpensive and have a wide range of features: http://www.knjn.com/ShopBoards_USB2.html
Xilinx has a lot of development boards as well.
My experience with Xilinx is better in the support department than Altera. They will give you the software and even dev hardware if you ask nicely. But their software takes more than 12 hours (yes twelve hours) to install and update on a core 2 duo machine. Sad really.
The altera software is lighter feeling but just as powerful and seems to be more
... what's the word: friendly. I haven't used Xilinx in a while but I had a hellofa time with it, when I was trying to prototype asics with Virtex II.
Altera is currently under mandate to make money from their software, even though they are a hardware company. That makes getting a free license almost impossible. Too bad for them.
I've been getting great support for Altera from Octera Solutions (as opposed to Altera itself). Perhaps they can help you.
If you're brand new to hardware, you might want to learn Verilog or VHDL first. I think both Xilinx and Altera's web kits come with Modelsim. Its a stripped down version but it will be fine to learn the basics.