will depend on whether the state in which they lived recognizes common law marriages or not. Some do (or used to, the last time I checked). If a state recognized common law marriage and a couple satisfies all of the requirements they are just as married as if they used the ceremonial process. Here's a link to the states which do (although I can't vouch for its accuracy, other than Ohio)
http://www.nolo.com/article.cfm/pg/2/objectId/709FAEE4-ABEA-4E17-BA34836388313A3C/catId/697DBAFE-20FF-467A-9E9395985EE7E825/118/304/192/FAQ/Ohio did until 10/10/1991. All you had to do was satisfy the following requirements: be legally eligible for marriage (which cuts out same gender couples), agree to be married, live together as married, hold out to the public that you were married, and be regarded in the community as married. Any couple which did that in Ohio prior to 10/10/1991 is still legally married - and would need to go through a divorce to terminate the marriage.
Different states have/had different requirements.