In 3rd season of Sherlock we come to know that there is a dark mystery associated with the past of Dr Watson's wife. How did Sherlock deduce that she was/is a CIA agent?
As @Bobby Alexander says, it's in His Last Vow, when Sherlock finds Mary holding Magnussen.
After she shoots him, he has a flashback to when he had met her in The Empty Hearse. In that episode, he said goodbye to her as she got in to a taxi. He did "his thing" and analysed her, with words flashing on screen to show the viewers what he saw. It looks like this:
In his flashback, however, he thinks of this scene again and is able to focus in on one word in particular:
This was the point then in The Last Vow at which Sherlock realised she wasn't who she claimed to be. However, it could be argued that he actually knew this from the first episode, The Empty Hearse, as somewhere deep down in his subconscious he knew this. He had already picked up that she was a liar, disillusioned etc. from that episode, but he had picked them up with so many other traits that they hadn't really "registered". Whether you feel this actually counts, or if his true understanding of her nature in The Last Vow was the real moment of realisation is obviously subjective.
Later in The Last Vow, Sherlock meets Mary after he gets out of hospital - it is there she officially confirms her hidden past as an assassin.
From the episode's script:
MARY: How much d’you know already?
SHERLOCK (still speaking more quietly than we’re used to): By your skill set, you are – or were – an intelligence agent. Your accent is currently English but I suspect you are not. You’re on the run from something; you’ve used your skills to disappear; ...
(John shakes his head as if he can’t believe what he’s hearing.)
SHERLOCK: ... Magnussen knows your secret, which is why you were going to kill him; and I assume you befriended Janine ... (he grimaces, shifting uncomfortably on his chair) ... in order to get close to him.
Later in the episode:
MAGNUSSEN: All those wet jobs for the CIA. Ooh!
So Sherlock clearly deduced she was an intelligence agent (or at least a former one), whilst Magnussen reveals it was the CIA - although it could certainly be argued Sherlock already knew this and that this revelation was to pinpoint exactly who she worked for for the benefit of the viewer.
While the other answers are correct about when Sherlock actually learned that there was something seriously wrong about her and when he came to deduce all the other information about her past, I'd still add that I think he had a suspicion about her all the time since they met.
When Mary and John leave him after his magical reappearance at the beginning of "The Empty Hearse", he does "his thing" on Mary and sees all those words flashing across his inner eye:
But the most interesting aspect of this scene is IMHO the slightly perplexed or thoughtful look on Sherlock's face after this. Given what we learned in "His Last Vow" it almost seemed like he sensed there to be something wrong or mysterious about her, but wasn't really sure what it was, not being able to filter it out of all the other information he learned about her (kind of like the opposite effect of his encounter with Irene Adler, revealing too much instead of too few information). So I think he sensed something strange about her but disregarded it for now or just stored it in his subconcious (or rather his mind palace of currently irrelevant information).
Later in "The Sign of Three" this is reinforced, I think. At the end of the episode, when Sherlock does one deduction too much and (accidentally?) informs John and Mary about their anticipated baby, he again seems to react slightly perplexed for a short moment. Now, in an episode where we learned much more about Sherlock's character and where his relationship with John was extended by an aspect far more emotional than usual for Sherlock, this might just have been a moment of realizing that their relationship will probably not remain at its usual course, now that it's not only a wife but also a baby. But knowing the information from one episode ahead, this moment is once again interpretable as a foreshadowing. Sherlock once again sensed that Mary maybe was not as happy about this information as she claimed, for whatever reason. Yet Sherlock still didn't know what to do with this information, nor dared to actually speak that out at the moment.
Now I agree that these are only very speculative hints, only deduced by knowing about the revelation in "His Last Vow". But in retrospect I think those little incidents were a foreshadowing about Mary's secret and the fact that Sherlock knew there was something wrong with her all the time, even if he didn't know what it was nor how serious that was, until his encounter with Mary in Magnussen's office.
Tagging onto Napoleon's answer about Sherlock having a fundamental intuition that something was wrong with Mary, I would suggest that he was tipped off by the fact that Mary was so strongly devoted to John that something was suspicious. In the previous season, we learn that John can't keep a relationship with a girlfriend, having so many that he forgets which one has a dog or not. He does not expose himself emotionally (allowing for deep relationships). So why would a woman who seems rather strong and independent be so attracted to John?
Then, the whole re-appearance of Sherlock and surprise at the restaurant...Mary's reaction is, IMHO, clearly portrayed as 'fake'...that is, from a script perspective, her character makes an effort to be surprised, but really isn't...tipping Sherlock off that she know exactly who Sherlock is. And again, why would a woman about to be engaged be so forgiving of such a major disruption, and she even tells Sherlock that she will help John come round!
Finally, my daughter picked up on this right away...Mary recognized Magnussen's messages as a 'skip code' when John was kidnapped...this is before the actual revelations come out...This would likely point to involvement in intelligence, cloak and dagger, or at a minimum, someone with a calculating mind.