The NYTimes article Threatening U.S., Putin Promises Russians Both Missiles and Butter says only this about Putin's recent mention of "deep state" in the US, in his state-of-the-nation speech:
Mr. Putin did not criticize President Trump, instead suggesting, as he has in the past, that a secretive “deep state” hobbled the American president.
Did he say more about it in this speech, and what has Putin said about a US "deep state" in the past? Does any of it predate the Trump presidency?
Here's the relevant full quote from The Presidential Address to the Federal Assembly:
[...] Russia wants to have sound, equal and friendly relations with the USA. Russia is not threatening anyone, and all we do in terms of security is simply a response, which means that our actions are defensive. We are not interested in confrontation and we do not want it, especially with a global power like the United States of America. However, it seems that our partners fail to notice the depth and pace of change around the world and where it is headed. They continue with their destructive and clearly misguided policy. This hardly meets the interests of the USA itself. But this is not for us to decide.
We can see that we are dealing with proactive and talented people, but within the elite, there are also many people who have excessive faith in their exceptionalism and supremacy over the rest of the world. Of course, it is their right to think what they want. But can they count? Probably they can. So let them calculate the range and speed of our future arms systems. This is all we are asking: just do the maths first and take decisions that create additional serious threats to our country afterwards. It goes without saying that these decisions will prompt Russia to respond in order to ensure its security in a reliable and unconditional manner.
That particular quote comes right before Putin wrapped up with a summary, making no other references to a presumed American deep state within the speech. As the NYT correctly noted, it's a very small portion of the overall address:
Mr. Putin took up his usual foreign policy cudgel at the end, using most of the 90-minute speech to Russian lawmakers to focus on improving the standard of living in Russia.
Putin made some remarks which could be construed as being about a deep state in a Q&A with journalists after Russian-Italian talks in Sochi, May 17th 2017:
[...] At the same time, however, we see the growing political schizophrenia in the United States. There is no other way I can explain the accusations against the current president that he handed whichever secrets over to Lavrov.
[...] They are using anti-Russian slogans to destabilize the internal political situation in the United States, but they do not realise that they are harming their own country. If this is the case, then they are quite simply stupid. If they do understand what they are doing, then they are dangerous and unscrupulous people. In any event, this is the United States’ own affair and we have no intention of getting involved.
Putin referred to an American deep state in an interview with Le Figaro, May 29th, 2017:
I have already spoken to three US Presidents. They come and go, but politics stay the same at all times. Do you know why? Because of the powerful bureaucracy. When a person is elected, they may have some ideas. Then people with briefcases arrive, well dressed, wearing dark suits, just like mine, except for the red tie, since they wear black or dark blue ones. These people start explaining how things are done. And instantly, everything changes. This is what happens with every administration.
...and in June 2017 in an interview with Megyn Kelly in St Petersburg:
"There's a theory that Kennedy's assassination was arranged by the United States intelligence services," he said. "So, if this theory is correct and that can't be ruled out, then what could be easier, in this day and age, than using all the technical means at the disposal of the intelligence services and using those means to organize some attacks? And then pointing the finger at Russia."
A quick Google search for putin american "deep state" results prior June 2016 also doesn't turn anything up.
In summary:
