It comes with practice in the field. After a few medium-size designs, you start to have some data-points for design-to-FPGA mappings. If you _really_ need to get close the first time, the only way is to mock up the design and synthesize it.
At places I've worked, the general pattern tends to be:
1) Pick a target FPGA family based on feature-set and advertising copy. Probably you use the vendor you're already familiar with.
2) Make an extremely rough LUT count estimate based on some prior designs (and/or maybe based on the utilization numbers for vendor-supplied IP cores).
3) Most FPGA vendors sell a bunch of variants of any given family. Do your first round of prototypes using an FPGA that is 50-100% larger than you think you need.
4) Once you've got the design more nailed down, make a better estimate and pick a smaller/lower-cost part in the same family. On FPGAs that I've used, the FPGA is generally 'full' if you've used up 75%-ish of the available LUTs. This is because of limited routing resources and imperfect compilers.