My advice is to borrow a book at the library. Most of the books on VHDL will cover the basics well but not teach all the nuances, and you really do need the basics because logic design is fundamentally different from imperative programming.
There are many simulation tools available to test your theories, including Xilinx WebPack (gratis) which you'll be using if you do get a Xilinx based board later, or GHDL for a free software example. Several books already come with an analysis/simulation tool.
Once you have a fair knowledge of the structure of the language, dig around for examples. Opencores.org is one place to look, and fpga4fun.com has basic examples. You may even want to head there first for links to tutorials, explanations and so on.
Edit:
Most projects won't be very interesting in simulation alone, so you'll quickly want to get some hardware to play with as well. These will have a bunch of concerns, such as purchase price, tool flexibility, and included peripherals. Kits like Spartan 3[AE] Starter have a fair range, from expansion ports through switches and LEDs to video and audio ports. Simpler ones like Papilio One may have nothing at all but what you add. Make sure you get the software side working, though, because there's little more frustrating than a limited time license to use what you paid for while it doesn't work.