1. Get a (the) Spartan-3 starter board. It's got the 500 variant of the Spartan-3 on it which is big enough to implement even small processors. The board also has some very limited VGA output, and a heap of other things that makes it fun to work with (Serial I/F, etc). The manual for this board is one of the better ones for beginners, as well. I broke my own teeth on this board. It's 149 US schmucks from digilent.
2. Get Xilinx's free tool suite; its nicely compatible with that board. Free download from the web. Heck, you can even download and play with it without the / any board (but then you don't, of course, get the blinkenlights.) You can however try out and simulate designs before going to FPGA, and thus figure out why the (redacted) it doesn't (redacted) work. Simulations are your main way of verifying your design once you're past 20-odd gates.
3. Learn the HDL of your choice. Read the books. One warning only: it is NOT a programming language - the entire model in your head about how software works needs to be replaced. Case statements are king. Productivity with HDL's are generally way lower than software; don't be surprised by this.
4. Do points 1 through 3 in reverse order. Having a shiny 150 schmucker board won't help anything if you still have to spend two weeks grokking HDL's.
HTH.