As ratchet freak said, the estimates are based on running the game on a set of different hardware configurations. Often, they will load a set of different game configurations on those computer systems as well. That way they can gather information such as "Game ABC runs at 72.4 fps on a system with CPU XXX, GPU YYY, with ZZZ GB of RAM, on Ultra High settings."
Not all pieces of a hardware configuration contribute equally to the framerate of a game. Often, the GPU is the most important factor, followed by the CPU, the amount of RAM, and whether an SSD is used or a standard HDD.
In terms of game configurations, two important factors are graphical fidelity (i.e. low quality graphics all the way to ultra high quality graphics) and display resolution (i.e. how many screens are you rendering to, and what resolution do they run at).
By obtaining a set of benchmarks on various systems, and in various game configurations, you can often extrapolate your data to different hardware configurations to make an estimation of the framerate on unmeasured systems. You could simply use the benchmark that is the most similar to the user's configuration (looking at the most important hardware components), or you could calculate a weighted average across multiple benchmarks based on similarity.