What do we mean when we say it today?
For whatever reason, nowadays, people usually switch the words around. People say: "Methinks the lady doth protest too much." Maybe that's because putting the "methinks" at the end makes the quote seem a bit more detached or dry.
But we've also switched up the meaning. Today, "protests" means "to object." Even though it didn't mean that when Shakespeare came up with the phrase, we now use this to mean someone is objecting or denying something way too much to be trusted. As in, they swear they didn't do whatever it is they swear they didn't do—but we know they totally did.
The funny thing is, most of the time, the end result is the same. Gertrude is saying the lady confirms her vows too much and loses her credibility. We say someone is objecting so much they lose their credibility. Either way, credibility is lost. It's just a whole different road to get there.