Nick Clegg, the Deputy PM attacked ‘naysayers’ in a speech earlier this week (see this headline). A naysayer is “a person who opposes something or who is generally inclined to act in a negative manner”, according to the OED. That is a relatively recent meaning of the word (20th century). In the 17th century it was mainly a Scottish word and meant “a refuser, a person who declines a request”.
Nay is a regional variation of the word no. Originally nay had a slightly different sense. It was originally the standard negative response given to a question asked in the affirmative (the positive response would have been yea). If the question was posed in the negative, then the correct answer was no (or yes, in the affirmative), so no was more emphatic. There is a 1532 citation from Thomas More in the OED which explains this distinction:
1532 T. More Confutacyon Tyndales Answere iii. p. clxxxi, No answereth the questyon framede by the affyrmatyue‥yf a man sholde aske‥is an heretyke mete to translate holy scrypture into englyshe‥he muste answere nay and not no. But and yf the questyon be asked‥Is not an heretyque mete to translate holy scripture into englysh. To this questyon‥he muste answere no & not nay.
The word yea-sayer is also in the OED. It dates back to the 1930s, and was clearly coined in response to naysayer. It is defined as “one who agrees or is inclined by nature to assent, or act in a positive manner”.