If you do not have a digital logic background, first spend a bit of time getting comfortable with that. One of the most common problems I have seen with programmers coding on FPGAs is related to that - even though verilog coding looks like its just software coding, like C with a weird syntax, it really isn't. Everything you write actually allocates additional physical hardware on the FPGA. Every piece of that hardware works all the time - in "parallel" so to say.
Once you are comfortable with ISE, and have used its built in simulator to make some basic designs, then think about buying one of the $100/$150 Spartan kits from Xilinx. Once again, before you plonk down any money, make sure you really want to do this - FPGAs sound really cool initially, but they are less useful in a computing sense than they initially appear to be. They are very useful as glue logic but thats not why most programmers get initially interested in them. FPGA vendors have been marketing FPGAs as general purpose computing devices, but except for some very specialized cases, you are almost always better off using an Intel CPU for example, or even a GPU.
When buying a board, keep a list of atleast 2-3 significant projects that you would want to implement on it - that way you can select a board with the right IO connections. The particular FPGA device on the board in less important that having the right IO connectors - these are very difficult to add later on if you are not a pro.
HTH.
A very large part of coding for FPGAs is to actually make your design work within very tight hardware limits, at a particular frequency, while satisfying routing contrainsts, very limited RAM, limited number of Fast Multipiers, etc.
So while Icarus would be ok when you are learning verilog/vhdl, it doesn't really help you learn any of the practical stuff.
To use a bad-car-analogy, its like learning to drive using a driving simulator on your PC, controlled with cursor keys instead of steering wheel. Yeah, I know. I didn't find that funny either :p