I found an FPGA board that I liked. It uses a Xilinx Spartan 6 LX45. When I went to the datasheet for the Spartan 6 series, it only said that there were 43,661 logic cells. How many gates does that equate to? Or rther, how would I figure out the number of total gates from the number of logic cells?
FPGA manufacturers don't use equivalent gate counts much any more, even in the hand-wavyest marketing materials. Like lines of code or megahertz of processor speed, it's a highly inaccurate metric for measuring the device capability, and in the FPGA markets the customers wised up enough to suppress its use.
To estimate the size device you need, you'll need to look at the summary on p. 2 of the datasheet you linked. Usually you can get a decent idea early on in your design process how many flip-flops, how many i/o's and how much ram your design needs. One or the other of those will typically be the critical resource that determines the size of part you need.
If you aren't tightly cost-constrained, use a device 2x or more bigger than you think you need. It will give you room for feature creep in your design and also speeds up development because the design tools won't need to work so hard to fit your design into the available resources.
Edit, pulling in things from comments,
You mentioned that your design is mostly unclocked.
The issue with this is that FPGA design tools depend on clocking and the resulting timing constraints to drive optimization of the synthesized design. If you want to do unclocked design in an FPGA it's possible in principle, but you're not going to get much help from the tools (or vendors) and you'll probably need to find a specialized community who do that kind of thing to get any support.
In any case, you can look at the Spartan 6 Configurable Logic Block User's Guide to see what resources are available in each block. Then mentally map your design to those resource to see how many blocks you need. That should be enough to let you pick the right size device.
For example, you can see in that document that the LX45 part contains about 27,000 6-input LUTs. Each LUT can be used to implement an arbitrary combinatorial logic with up to 6 inputs. If you can express your logic in terms of this primitive, you can estimate whether your design fits into the device.
FPGAs are more than just gates (LUTs, FFs, Block RAM, Multipliers, etc) and trying to work out how many there are is a fairly meaningless exercise. FPGA company marketing departments have, in the past, thrown numbers like equivalent gate counts equal to 1.4x the number of logic cells but I believe that they have stopped this practice.
If you are trying to determine whether a given design will fit in a FPGA it is best to do some trial synthesis runs on your HDL for various size FPGAs.
Come at it the other way - it sounds from other comments like you have a module already sorted out. Feed that to the FPGA tools - even the no-cost ones will give you an estimate of LUT/BRAM/FF count from the synthesis. Multiply that up by your instance count, add some slack and there you have a usable LUT count for sizing the FPGA.
Of course, you may have to do it for each type of FPGA you consider as they each have somewhat different architectures, in terms of the number of inputs the LUTs have, and how much other supporting circuitry in the way of muxes etc they have around the LUTS. And whether your circuit can take advantage of it...