<p>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:</p>

<ol>
<li>Do you prefer VHDL or Verilog and why?</li>
<li>What is a good way for one with no prior experience in HDLs get started in learning such a beast?</li>
</ol>

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.