Can anyone confirm whether Section 31 ever appeared in a Star Trek: The Next Generation episode?
Q. Was there any debate about whether or not to establish that [Section 31, in "Inquisition"] has been around for so long?
A. We had extended conversations about the backstory to Section 31 and yes, there was a lot of debate about how long and under what circumstances this branch had existed.
That being said, Section 31 comes into conflict with the crew of the TNG Enterprise a few years after Nemesis in the EU novel Star Trek: Section 31: Control.
Data felt great pride at the progress his daughter had made in so short a time. When he was her age, he had still been struggling to master basic interactions with organic sentient beings. By contrast, Lal meshed easily with organic beings, and in spite of what Data had originally considered her fragile emotional state, she was demonstrating tremendous calm and poise in the face of a serious and perhaps even existential threat from Section 31.
As @Valorum already stated, 'Section 31' as a department was thought up during DS9's run, but in-universe the organisation, or specifically the article in the Starfleet charter that lends its name to the covert-ops branch, has existed since the very beginning. Here's a quote from the Star trek: Enterprise episode Divergence, where Phlox is ... involuntarily re-assigned.
ARCHER: Phlox was kidnapped. Starfleet would never authorise that.
HARRIS [on monitor]: Reread the Charter, Article 14, Section 31. There are a few lines that make allowances for bending the rules during times of extraordinary threat.