...then how were gays never married before if they always had the right to marry?
Social Pressure and laws taking away their rights to be publicly gay. Many of these laws were enforced because of cultural or religious pressures. In fact gay marriage has existed as long as marriage. From wikipedia.
"Same-sex marital practices and rituals were recognized in Mesopotamia.[72] Some ancient religious Assyrian texts contain prayers for divine blessings on homosexual relationships.[73][74] The Almanac of Incantations contained prayers favoring on an equal basis the love of a man for a woman and of a man for man.[75][76]"
and
"The first Roman emperor to have married a man was Nero, who is reported to have married two other men on different occasions. His first marriage was with one of his freedmen, Pythagoras, to whom Nero took the role of the bride." (although romans did not give rights to same sex marriage as they did opposite sex marriage.)
The point is you have the right to do anything humanly within your power. Governments do not grant rights, they take rights away. Sometimes this is done to protect our young, sometimes this is done to make society work (losing your right to kill other humans). The point being that the government must be held accountable for the rights it takes from us. They should do everything in our power to leave us with as many rights as they can without bringing down society.
A good test for determining if a right should be taken away is if it harms other people and stops them from executing their rights. Allowing gays to marry does not constitute a physical danger for people nor does it impose on their rights to do whatever they want. With this in mind there is no reasonable logic behind removal of these rights.
The US government is designed to protect our rights more so than any government before it. I'm glad to see congress has decided to protect the rights of states to decide who can get married and do the right thing, respecting the decisions of those states.