The nerdy details: Norwegian researchers collected physical measurements for 2067 healthy men and 2193 healthy women aged 20 to 90. They established VO2(max) (actually peak oxygen uptake) by running each participant to exhaustion. They then used multiple linear regression to build a statistical model to predict ground truth VO2(max) from the collected measurements. They reserved some of the data as holdout for validation of predictive ability. The final models are segmented by sex; and predict VO2(max) from age, frequency/intensity of physical activity, waist circumference, and resting heart rate. Overall coefficient of determination (R squared) was 61% for males and 56% for females.
I'm guessing your 'fitness age' is determined by calibrating VO2(max) to age: for all men of a given age, calculate the average observed VO2(max), and report the age whose average VO2(max) equals the value that was predicted for you.
The methodology seems legit: The experimental protocol is of high quality, the sample seems representative of a wide range of (healthy Norwegian) individuals, the model is not overly complicated for the sample size. The coefficients on the predictors have the right sign. I suppose the researchers could have achieved a better fit by trying out various transformations for the predictors, but perhaps they wanted to keep the model simple.
Link to research paper: https://helseforskning.etikkom.no/ikbViewer/Content/178531/Article_HUNT_model_for_VO2peak.pdf