Programming a DSP is similar to programming any other type of microcontroller, except that it is designed with signal processing in mind. As such it is designed with extra multipliers and pipelines to allow faster signal processing. They also (some do) come with software libraries to implemented tested signal processing functions such as the fourier transform, and convolution.
An FPGA is exactly what the name suggests: a programmable gate array. You program it as a piece of hardware. The FPGA basically implements look up tables and as such is good for doing complex logic very fast. Using languages such as VHDL and Verilog you can create complex logic structures. Many pre-writen FPGA cores exist that allow you to implement processors, multipliers, video/audio converters, network protocols... just about anything. So an FPGA is extremely flexible. If you are looking to implement a complex system, then an FPGA is what you want.
If you are using signal processing, and are testing an algorithm then a DSP would be best, as reprogramming an FPGA for signal processing tasks isnt as easy as it is for a DSP. You could how ever develop a DSP like FPGA core, but this would require extensive effort... and unless you understood your algorithm well would waste development time.
In the past I have with ease used an FPGA to build a system containing a processor, ethernet, serial ports, and 100s of digital I/Os... this is exactly what they are suited for.
Where as if i were building a digital equaliser for example, a DSP would be best.