While FPGA makers don't just throw their formats out there, there is extensive documentation at a low level. Xilinx devices are a good example.
To reverse engineer the bit stream you might generate test cases that implement simple logic and see how those translate to the bit stream, then move on to designs that exercise different portions of the chip.
At the basic level, you would want to know how a CLB is controlled then the IOBs and interconnects. the CLBs are the logic the IOBs the are connected to the pins and interconnects link up the CLBs and IOBs. This document should give you a lot of insight into how FPGAs are implemented and how you might go about reverse engineering the bit streams. Do note that newer FPGAs are moving to 6-input luts rather than 4-input as was common.
Just keep in mind that the bit stream isn't software - it is a hardware configuration image. So, it's actually very similar to how ENIAC must have been programmed - rewiring circuits and flipping switches to program it - except in this case you are setting up routes with interconnects and logic in the CLBs.
Also the guy behind the Ben NanoNote is writing a fpga-toolchain which I am following avidly. Since a secondary to my SparcStation collecting hobby is reimplementing sun4m, a SparcStation architecture, in FPGA. After all who wouldn't want to be able to configure an FPGA from an FPGA with your own processor design on it.
Update: It's worth noting that IceStorm (mostly ice40 chips) and NextPNR (Multi targeted at ice40/ECP5/Xilinx Series 7) are the current state of the art reverse engineered FPGA toolchains.
"if it implements a soft processor - in that case there should be firmware for that"
.... but a soft processor isn't firmware (what processor would run that firmware?) It is a configuration of hardware elements on the FPGA.