People would sell piglets and would try to sell "a pig in a poke" (where a poke is a bag).
That's why you don't buy a pig in a poke because you can't see what you're buying.
Letting the cat out of the bag is because you've revealed that it was a cat rather than a piglet. You've revealed the deception.
I've actually seen the "genie back into the bottle" phrase used in contexts that refer to secrets, e.g. where "the cat is out of the bag" would actually be more appropriate, so there's definitely some overlap there. For example, I've seen people talking about nuclear proliferation say "you can't put the nuclear genie back into the bottle", meaning that the secret of how to build a nuclear weapon is well-known, and it's not really possible to make it secret again. But I've also seen people use the same "you can't put the nuclear genie back into the bottle" expression referring to a nuclear weapon exploding: once the radioactive material in the bomb has gone critical, there's nothing anybody can do to stop the explosion that's about to happen.
Personally, I like the "genie back into the bottle" phrase better. But some people like more grounded-in-reality phrases rather than fantasy-based phrases, and they prefer "toothpaste back into the tube". Either one works well, though.