Where did that phrase come from? Several pirate web sites and even a few books on pirates say that it refers to the cat o' nine tails being taken out of its canvas bag.
I disagree.
One reason I don't believe this is that it is not the explanation I grew up with. When I was in grade school I heard that this expression was paired with "pig in a poke". According to this explanation, someone would show up on market day with a piglet in a "poke bag" (an old expression for a bag). The buyer was cautioned not to open the bag or the piglet would get loose, thus a "pig in a poke" meant buying something unseen.
Sometimes the contents of the bag got loose and turned out to be a cat instead of a piglet. That "let the cat out of the bag" - it revealed a secret too soon.
The general usage of the phrase agrees with the pig in the poke version. The first recorded use was in 1760 in the London magazine:
"We could have wished that the author... had not let the cat out of the bag."
This has nothing to do with punishment and the cat o' nine tails version doesn't have anything to do with revealing surprises.
I'm even skeptical about the cat o' nine tails being stored in a bag. If you keep leather in a bag it develops curves, especially if it is put away wet. For best results you would want it straight. This is best done by hanging it by the handle.
As further confirmation, the French have their own version of the pig-in-a-poke/cat-out-of-the-bag saying:
"acheter chat en poche" (="buy a cat in a bag").
So where did the cat o' nine tails version come from? This message board attributes it to CANOE (the Campaign to Attribute Naval Origins to Everything).
Another example of CANOE - the "square meal'. This is often attributed to the Royal Navy serving meals on a square trencher. Actually, it means a "fair meal". "Fair and square" were used together and interchangeably for some time. Look at FDR's "Square deal". This may have come from cockney rhyming slang.
I also saw the phrase "you scratch my back and I'll scratch yours" attributed to being flogged with the cat o' nine tails. The idea was that if you go easy on me, I'll go easy on you when your turn comes.
I don't accept that one either. The phrase needs no further explanation. The middle of the back is hard to reach and a really bad itch requires someone else to scratch it. The phrase means "If you do something for me, I'll do something for you." Common usage does not agree with the flogging version.
While I'm on the subject, "rule of thumb" isn't quite a nautical phrase but you would expect a ship's carpenter to use it. It means a rough measure. In the 1970s, a feminist invented a new meaning - that a husband could beat his wife with a stick as long as it wasn't thicker than his thumb. In this usage, the word "rule" changes meaning. Again, it does not agree with how people actually use the phrase.
UPDATE:
While I'm talking about cats, I should mention the phrase "not enough room to swing a cat."
The actual derivation of this phrase is lost. It is often attributed to swinging a cat o' nine tails but this cannot be correct. Flogging was done in public as a lesson to the rest of the crew. The sailor was tied to the main mast on the open deck where there was always enough room to swing a cat o' nine tails.