This article is from the FAQ, by with numerous contributions by others.
The spouse of a US citizen gets a CONDITIONAL green card "immediately"
after marriage. After 2 years, the conditionality of this green card
is removed(after successfully proving to INS that the marriage is
legitimate). The spouse is eligible for his/her citizenship after
3 years of receiving the CONDITIONAL green card.
In a nutshell,
3 years after obtaining one's green card(including the CONDITIONAL one)
If you want to get more technical ["technical" may not be
the right word :-)]
(a) Any person whose spouse is a citizen of the United States may by
naturalized upon compliance with all the requirement of this title
except the provisions of paragraph (1) of section 316(a) if such
person immediately preceding the date of filing his application for
naturalization has resided continuously, after being lawfully admitted
for permanent residence, within the United States for at least three
years, and during the three years immediately preceding the date of
filing his application has been living in marital union with the
citizen spouse, who has been a United States citizen during all of
such period, and has been physically present in the United States
for periods totaling at least half of that time and has resided
within the State or the district of the Service in the United States
in which the applicant filed his application for at least three months.