I am a self-taught embedded developer. I mostly use AVRs programmed in C and ASM, but I have dabbled with other systems. I am looking to move onto more complex devices like CPLDs and FPGAs, but I have no idea where to start. So my one and a half questions are:
Buy a cheap starter kit from Xilinx or Altera (the two big FPGA players). A Xilinx Spartan3 starter kit is $200.
I personally prefer VHDL. It is strongly typed and has more advanced features than Verilog. VHDL is more popular in Europe and Verilog is dominating in the US.
Buy a book (e.g. Peter Ashendens The Designers Guide to VHDL) and start simulating your designs in a free simulator. ModelSim from Mentor Graphis is a good one and there are free versions available (with crippled simulation speed).
Make up some interesting project (mini cpu, vga graphics, synthesizer) and start designing. Always simulate and make sure your design works before putting your design into the hardware ...
If you have no background in digital electronics buy a book in that subject as well.
Also check out opencores.org - There are some articles and a lot of open source code in both Verilog and VHDL you can learn from.
As far as I can tell, VHDL vs Verilog gets just as religious as Ruby vs Python or Java vs C#. Different people have their own favourites.
Back in the day when I worked on ASIC design, it was in verilog. In many cases as a designer you don't get to choose: the ASIC synthesis tools for an HDL cost a substantial amount of money, and companies only purchase the full toolchain for one "blessed" language. My employer had standardized on verilog, so that is what we used.
FPGA synthesis tools are substantially cheaper, so you have more freedom as an FPGA designer to pick your favored language and tools.
There are also free verilog simulators available at verilog.net.
As @kris mentioned, an FPGA starter board is also a good way to go. Having your verilog code light up an LED on a board is infinitely more satisfying than a simulator waveform on the screen.
One additional thing to think about is whether you should start by learning an HDL, or by learning boolean logic, Karnaugh maps, DeMorgan's theorem, gates, implementing arithmetic in gates, etc. It's easy to write non-synthesizable HDL if you don't have an accurate mental model of what the underlying hardware will look like.
This book is the Verilog version of the one I used in undergrad, and it did a pretty good job in my opinion. It starts you out with the material mentioned above, as well as some basic, basic info on the transistor-level implementation of gates, then introduces you to an HDL, and has you build progressively more complex structural and behavioral hardware blocks. Yes, I know it's ungodly expensive, as are most college textbooks, but this is one of those things for which the information I've been able to find online, at least, has been woefully inadequate.
Once you're ready to choose an HDL, I heartily recommend Verilog (having learned VHDL first). Yes, VHDL was once much more feature-rich than Verilog, but later revisions of the language (Verilog 2001, Verilog 2005, SystemVerilog, etc..) have cherry-picked most of the interesting features, and there is far more robust toolchain support for Verilog and its variant these days, in addition to it being the dominant language in use in the US (in my experience, VHDL is only used here when dealing with extreme legacy blocks, and in academic contexts, partially due to the tools support mentioned previously). Finally, once you've learned the HDL, you have a hardware verification language (HVL) in SystemVerilog with strict-superset syntax, saving you a good bit of the learning curve. Not so for VHDL, to my knowledge.
Altera and Xilinx have simulators build into their free tool sets. They are limited versions of the very popular Mentor ModelSim tools. They will handle the size of designs you are likely to get to fit in a < $500 (US) board.
For HDL choice Verilog is to C as VHDL is to ADA. So Verilog is easier to get started with, but you can make mistakes more easily. Check your simulation and compilation warnings to avoid those problems.
Check out this site: http://www.fpga4fun.com/
Nice simple projects using simple tools. I used one of these boards a few years ago to build a small VGA display system for use as a notice board.
Looking at the site again I'm thinking of getting a Xylo-LM board as it has an ARM processor as well as SDRAM and a Xilinx Spartan 3e.
Another board I used before was the XPort 2 from Charmed Labs. This plugs into a Gameboy Advance which is well supported with open source development tools.
Verilog is much easier to learn and simpler syntax. Its also a newer language. Secondly, most people use verilog. VHDL has many datatypes which give it a learning curve. Once you know verilog it will be easier to bridge the gap to VHDL. Oh and theres also macros in verilog which are very neet. I invented a language with it. Finally, you will eventually be able to do mixed language HW design. I started out with VHDL, then learned verilog and am now pro verilog.
Before plunging into Verilog/VHDL or buying an FPGA dev kit I'd recommend taking an introductory class on digital design. There are good online OpenCourseWare MIT classes.
Good luck.