"I lived in a world of secrets. Of sabotage and deceit.
I spent so much time erasing my movements, covering my tracks...
and now that I look back at my life, I find... nothing. It's as if I never really existed.
I cheated you all out of being in my life. And what's more, I cheated myself as well."
Section 31 Deputy Director Luther Sloan,
Extreme Measures (Star Trek: Deep Space Nine)
Section 31 doesn't exist in the Star Trek universe, at least not officially. Starfleet Command refuses to acknowledge its existence and yet stubbornly refuses to deny it as well.
The organization is one of those agencies created more through bureaucratic oversight than any desire to do harm. Article 14, Section 31 of the Starfleet Charter allows certain constraints of the document to be conveniently bypassed during times of war or threat (sounds eerily familiar, don't it?). Section 31 is an outgrowth of that document and operates outside the boundaries of Federation Intelligence. They are answerable to no one and their resources are vast. They have no headquarters, no definitive power structure and no official mandate. What they do have is a plan, an almost unlimited resource base and, if I do say so myself, really snazzy leather uniforms.
Our first contact (timeline-wise) was through Malcom Reed, the Enterprise NX-01's security officer. Reed was a member of Section 31 (or one of its precursors) before taking a posting on the Enterprise. This didn't matter much until 2154, when Reed was reenlisted by a Section 31 agent by the name of Harris. Harris bartered a deal with the Klingons in order to halt the advance of a genetic disease, the same disease that conveniently explained why Klingons in The Original Series look absolutely nothing like Klingons from The Next Generation without having to admit that it had something to do with the prosthetics technology used behind the scenes. Harris, aided by the kidnapped Enterprise Chief Medical Officer, Dr. Phlox, needed Reed to buy the Klingons enough time to cure the disease.
Section 31 was also responsible for supplying information on Terra Prime, a group of xenophobic humans bent on driving all aliens from Earth, to Starfleet Command.
- - -
Jumping ahead a few hundred years, 31 was probably behind Starfleet's attempt to develop an interphasic cloaking device that would allow a cloaked ship to pass through normal matter as well as being rendered undetectable to conventional sensor systems - I say probably because the organization behind the cloak's creation was never mentioned by name but way only referred to as "A secret section of Starfleet Security," but I can't think of another mysterious Starfleet organization, so.
The only existing prototype of this device was installed on the USS Pegasus (under the command of then-Captain Eric Pressman, a man who may or may not have been an agent himself) and was later recovered by the USS Enterprise-D after the Pegasus rematerialized inside an asteroid.
- - -
Of all the storylines that involve Section 31, the most involved was their fascination with Deep Space Nine's Chief Medical Officer, Dr. Julian Bashir. Fascinated by Bashir's genetic enhancements and thinking that they would make him an formidable agent, Section 31 operative Luther Sloan attempted to recruit Dr. Bashir into their ranks in 2374. Bashir refused on ethical grounds and, after informing his commanding officer of the attempt, was instructed to keep an eye out for further Section 31 involvement in, well, whatever.
Bashir was contacted by Sloan one year later in 2375 as part of a plot to place a Section 31 agent in the Romulan Senate. Not that Bashir knew that or anything, but that was the eventual outcome. Sloan was successful thanks to the help of Admiral William Ross.
31 was (last one, promise) also involved in the attempt to kill off the Founders, (Odo's people) through the use of a morphogenic virus that attacked them at the molecular level. 31 developed the virus for Starfleet Security and infected Odo with it; Odo then transferred it to another Founder and from there to the entire Founder race. Bashir was able to (and here the admittedly dubious science of the Star Trek franchise gets completely out of hand) go inside Sloan's mind in order to find a cure. He does, though the attempt indirectly results in the death of Agent Sloan. To be totally accurate, Sloan attempts to kill himself to keep his secrets his, and Bashir enters his rapidly decaying and unstable mind to try to find them. Sounds cooler that way, don't it?
Purely from a writer's perspective, the existence of Section 31 allowed Starfleet officers to be brutal, conniving and vicious without all of them being seen that way. It's clever - the dangerous part is in falling back on historical revisionism (as silly as such a term is when applied to a fictional world) - it would be easy to assume that unvirtuous behavior on the part of a Starfleet officer was obviously the result of a group of rogue agents instead of Starfleet having the same potential for evil and avarice than any other race and that's just...really depressing.