I'd go with Spidermonkey's theory, that Mary Gordon may have had a (illegitimate?) child before her marriage to John Stewart in 1869. You could check the marriage cert on line at Scotlands People to confirm her marital status at the time of her marriage. The cert will also include full details on her parents' names which will help in tracing her family line back.
I can't see a marriage between a Gammie and a Mary Gordon on IGI.
Going solely on the place of birth showing for her on the later censuses, this is the closest entry I can see in 1861:
Mary Gordon, 27, domestic servant b. Inverkeithnie, Banffshire working at the Andrew household in Forgue, Aberdeenshire.
Monica