n the middle of sessions for Kid A, the still untitled song was introduced to the band by Thom and Ed's Diary mentions the song twice:

thursday, july 22nd 1999
thom arrives & plays a new song on the acoustic. sounds great but has no name, so now on referred to as the song with no name. we move on to "lost at sea/in limbo" after only nine months work its starting to sound like its getting somewhere. good in fact. The others sound ok too.( everything, everyone/the national anthem). highlight of the day is attempting 3 part harmonies on "neil young *9"- not the harmonies themselves, but phil cracking up because he feels a bit like that drummer from the eagles. a fucking brilliant rehearsal. its great to be in our band.

thursday, july 29th 1999
warts and all, warts and all......... the last two days were brewing up to this.....working on 'up the ladder'. 30 seconds into it & it sounds utter shite. thom stops it. lack of energy. phil gets pissed off. we talk a bit. start up again with a dose of the 'fuck you's. sounds better almost immediately. funny that. oh and the new song from 22nd is called 'move along' for the moment. also played the cminor. lovely sunny day.

In spring 2001, at the time Amnesiac was released, a piece of text that probably was the basis for the lyrics appeared in the 'imaginery prisons' section of radiohead.com:

On August 18th 2003, a simple version with just Thom on acoustic guitar was released under the new title 'Gagging Order' on the second of Go to Sleep singles. It was paired with 'I am a Wicked Child', another song that was around during the Kid A sessions already.
The engineering credit for Graeme Stewart points to the rehearsals for Hail to the Thief in spring 2002, and in 2008 Ed confirmed that the released recording indeed comes from that period.

Thom: "I was gagged. I had a gagging order served on me. Indirectly, at one point. Over something, which I obviously can't tell you about. But I have to say gagging orders are the most unpleasant legal invention known to man. They are sick. They are bad news… It just amazes me that if one lives in democracy you are still… you can basically be gagged. And when you're gagged, you're gagged. That's it."

On May 1st 2006, the song was played live for the first time at the Friends Of The Earth/Big Ask benefit show at the Koko in London. This video was edited from multiple sources for this website: