"It is time for people to wake up and smell the milestone," he told reporters before the session began. "If you would've told me two years ago that the state Legislature, under Gov. Christie, was poised to pass a marriage equality bill, I would've told you you were nuts. We can't even keep up with our own predictions."
Lawmakers have until the end of the legislative session, in January 2014, to try to wrangle the two-thirds vote needed in the two Democratic-led chambers to override the veto.
Goldstein and other gay-marriage supporters were bullish Monday that they'd find the votes.
"I'm telling you, we can override, we will override," Senate President Stephen Sweeney (D., Gloucester) said at a news conference following the vote. "We'll get there. This is only the beginning."
Overriding a Christie veto could be tougher in the 80-member Assembly, where Democratic sources said the bill may pass by only a few votes. Democrats, who have 48 seats there, would need to muster 54 votes to override a gubernatorial veto.
The Senate vote came the same day that the governor of Washington state signed a gay-marriage bill into law, making it the seventh state, along with the District of Columbia, to permit same-sex marriage.
New York approved same-sex marriage last summer, and Republican state lawmakers there who crossed the aisle to support the measure have received a boost in donations from the gay community.
Goldstein said that GOP lawmakers in New Jersey could expect similar support if they helped pass gay marriage.
"You should expect that Garden State Equality and our national allies will play a very vigorous role in 2013," he said.
On Monday, two Republicans voted in favor of gay marriage, including Sen. Diane Allen of Burlington County, while two Democrats voted against it.
A majority of New Jerseyans support gay marriage: 54 percent, according to a recent poll.
But by a similar majority - 53 percent, according to a Rutgers-Eagleton poll released Monday - New Jerseyans also support Christie's proposal to put the question to voters.
Democratic leaders in Trenton have denounced the idea, arguing that civil rights issues should never be decided at the ballot box.
The last time New Jersey voted on an equal-protection issue was 1915, when voters rejected women's suffrage by a 2-1 ratio, Sen. Loretta Weinberg (D., Bergen) said during the session Monday. Five years later, the 19th Amendment to the U.S. Constitution allowed women to vote.
Weinberg, who, with Sweeney and Sen. Raymond Lesniak (D., Union) led the gay-marriage effort, argued against "abdicating leadership when it gets hard."
Goldstein and other advocates wiped tears from their eyes as Weinberg said she would vote yes not just for her gay friends, but for her grandchildren, who deserve to grow up in a world where love trumps "fear and hatred."
"Those of you who are on the fence, I implore you to join with us on the right side of history," she said.
Sweeney, who used his power to resurrect the issue, urged his Republican colleagues to vote their conscience rather than make a political calculation - as he acknowledged he did when he withheld his vote in 2010 and gay marriage was rejected, 20-14.
"Yes, if you vote against this measure, you might keep your elected position and keep the support of those who are important to your ability to maintain office and push through legislation," he said. "But at what cost?
"Isn't it more important that we, as elected representatives, did something that truly changed people's lives for the better? I am not talking about tax policy, or paved roads, or ribbon cuttings. I am talking about real, true change in the way we treat each other as human beings."
Sen. Gerald Cardinale (R., Bergen) said marriage has always been defined as a relationship between a man and a woman. He called the bill a "Pandora's box" that, once opened, would lead others in nontraditional living situations to want the benefits of marriage.
What if two brothers living together, or a father and a son in the same house, wanted to apply for a marriage license? he asked. Cardinale noted that incest negatively affects society, a comment that drew groans and snickers from the gay marriage advocates.
The Senate would need three more votes to override a veto.
Two Democrats voted against the bill: Sen. Ronald Rice of Essex County and Sen. Jeff Van Drew from Cape May County.
In an interview, Van Drew, a Roman Catholic, said he believed the term marriage should be restricted to a heterosexual relationship. He said he supported strengthening the state's civil union law. Rice could not be reached.
John Tomicki, president of the New Jersey Coalition to Preserve and Protect Marriage, said the citizens should vote directly on gay marriage.
"It's for the citizens to vote on how they wish to define marriage," he said, adding that he had recently spoken with Van Drew and Rice about strengthening the civil union law.
Two Democrats who had voted against the bill in 2010 voted for it this time.
Sen. Fred Madden of Gloucester declined through a spokesman to discuss his change of heart. Sen. Shirley Turner of Mercer County could not be reached.
Along with Allen, Republican Sen. Jennifer Beck of Monmouth County also voted for the bill.
Allen, who was undergoing cancer treatment when gay marriage last came to a vote, said she believed it to be an issue of fairness.
"As I spoke to more and more people, I came to feel that the problems faced by these couples who wish to marry fit into the parameters of discrimination," she said in an interview Monday. "And I have always fought against that."
The Republican caucus told members to vote their conscience, and Allen said she wasn't criticized for her vote and Christie never tried to talk her out of it.
New Jersey lawmakers approved civil unions in December 2006 after the state Supreme Court ruled that denying the rights and benefits of marriage to same-sex couples ran afoul of the state constitution.
But civil unions haven't offered gay couples equality, marriage advocates argue. They are still sometimes denied access at hospitals, for example.
Donald Barb, 64, of Stockton, Hunterdon County, said whenever he fills out forms he is offered three choices: married, single, other. He writes in civil union, he said, to acknowledge his partner of 29 years.
"In the state of New Jersey, it's not understood and it's not recognized," he said prior to the session.
His partner, the Rev. Bruce Davidson, 63, said the vote in the Senate was a big step, even if Christie closes the door on gay marriage in the short term.
"There's hope, the ball is in motion," he said. "If it passes and the governor vetoes it, it's still alive for the next two years."
Contact staff writer Joelle Farrell at 610-627-0352 or firstname.lastname@example.org.
Inquirer staff writer Matt Katz contributed to this article.