As always ***SPOILER ALERT***
The Woman first comes to the attention of Sherlock in the episode "Scandal in Bulgravia." Or does she?
In "The Great Game," Sherlock receives a letter which he notes was written on Bohemian paper. The fact Sherlock initially says Bohemia and not Czech Republic could be more than just an nod to "A Scandal in Bohemia." I believe it is a clue pointing us in the direction of The Woman. After all, Sherlock also points out that the letter was obviously addressed by a woman.
The Bohemian paper could just be a playful red herring by Gatiss and Moffat, and some other woman could have addressed the letter under the direction of Moriarty. However, there are other allusions to "A Scandal in Bohemia" in this episode. Sherlock is able to guess Molly's weight gain (just as he does with John in "His Final Vow"), and the line "I'd be lost without my blogger" is an updated version of the line "I am lost without my Boswell" in the aforementioned short story. Lastly, the first time Sherlock receives a call from the bomber, the villain makes the person doing the talking call Sherlock "sexy." In the very next episode, The Woman states that "Brainy is the new sexy."
Could it be that The Woman becomes involved in The Game much earlier than we have been led to believe?