Most dictionaries mark this verb — to deny or contradict — as formal or literary; some go further and suggest it’s archaic; the Oxford English Dictionary, in an entry written over a century ago, stops partway, describing it as “slightly archaic” (is that like being a little bit pregnant?).
The number of times the verb turns up in books and the better sort of newspapers might make you doubt that verdict, but inspection shows that it’s formulaic and almost always used in the negative, in forms such as no one can gainsay or it is impossible to gainsay. Positive cases are rare and remarkable and do feel archaic:
One can gainsay de Gaulle’s conclusion, or at least his overall description of the profession of arms, without contradicting his general — and even obvious — point that history can be interpreted at one level as the history of ‘force’.
The Warrior Queens, by Antonia Fraser, 1988.
The word is a compound of the verb say with the most definitely archaic prefix gain-, against. This came from an Old English word that’s related, for example, to modern German gegen, against; it is a close relative of again, and turns up also in against itself. So gainsay literally means to speak against something.
The verb has largely lost its mental associations with say. Though its forms conform to those of the root in writing — gainsaying, gainsays, gainsaid — they don’t in speech, because they’re so rare that people say them as they’re spelled. Gainsays rhymes with days and gainsaid with shade (which is why it also appears as gainsayed).