Use of the term dates back decades, and it's popularity accelerated through Bush the Younger's reign (for obvious reasons I think, Bush was widely perceived as an idiotic puppet, a theatrical figurehead for the real government (e.g. Cheney and co.))

https://books.google.com/ngrams/graph?content=deep+state&yea...