The researchers broke things down into 2 studies. The first looked at variations in the gait between women at high and low conception probabilities. They conducted a motion capture study, recording the kinematics of their walking patterns. They repeated this procedure during the late follicular stage and the luteal stage with the women who were not using hormonal contraception. They found that there were significant differences in the walks of women at "high fertility risk" (naturally cycling and late follicular stage) and naturally cycling women at "low fertility risk," with no differences between hormonal birth control groups and high fertility risk groups. They speculate that these differences may be related to "fluctuations in personality dimensions" in women not on hormonal birth control like extroversion and agreeableness. I suppose if you are pissed off at the world then you have an angry walk. Grr.
In Study 2 the researchers asked men to rate the attractiveness of the walks. The men were not told the hormonal states of the women, just that they were rating women (point-light walkers of women) for attractiveness. They found that men were significantly more likely to rate women not using hormonal birth control as more attractive in their luteal phase. So men are judging naturally cycling women to be more attractive at a stage of low pregnancy probability. Seems a bit evolutionarily backwards, right? The authors speculate that this is a defense mechanism against sexual assault - broadly (and from far away) advertise that you are attractive when you are not actually fertile. Other studies show that other changes (body odor, facial attractiveness, etc.) increase in fertile times. The authors propose that these are more specific, closer cues that women share with men they are actually interested in.
How about a study about the walks of women who study the walks of women?
Provost Meghan P., Vernon L. Quinsey, and Nikolaus F. Troje. (2010) Differences in gait across the menstrual cycle and their attractiveness to men. Archives of Sexual Behavior: 37(4), 598-604. (DOI: 10.1007/s10508-007-9219-7)
(images from ovulation-calculator.com and examiner.com respectively)