Federal tax law doesn’t itself contain a definition of what constitutes a marriage, rather deferring to state law. As Reg. §301.7701-18(b)(1) provides:

(b) Persons who are lawfully married for federal tax purposes.

(1) In general.

Except as provided in paragraph (b)(2) of this section regarding marriages entered into under the laws of a foreign jurisdiction, a marriage of two individuals is recognized for federal tax purposes if the marriage is recognized by the state, possession, or territory of the United States in which the marriage is entered into, regardless of domicile.

(2) Foreign marriages.

Two individuals who enter into a relationship denominated as marriage under the laws of a foreign jurisdiction are recognized as married for federal tax purposes if the relationship would be recognized as marriage under the laws of at least one state, possession, or territory of the United States, regardless of domicile.

Technical Advice Memorandum 201734007 answers a question regarding whether the IRS had to recognize a “common law” marriage.

A minority of states recognize a common law marriage, which is a legally recognized marriage between two individuals who did not obtain a marriage license and did not have a recognized marriage ceremony.

The National Conference of State Legislatures published a list of states that recognize common law marriages in a web article published in August of 2014.[1] Per that list, the following states have common law marriages currently:

Colorado
Iowa
Kansas
Montana
New Hampshire
South Carolina
Texas
Utah

As well, the site lists the following states that previously recognized common law marriages and continue to recognize those old marriages in their state as valid:

Pennsylvania
Ohio
Indiana
Georgia
Florida

In the case in question, there was some concern about whether an arrangement qualified as a common law marriage under state law, so a state agency was consulted. As the facts provide:

In an Order dated Date 2, the State Board of Finance and Revenue concluded that Decedent and X had entered into a common-law marriage under State law and that “based on the specific facts and circumstances presented, Decedent and X were common-law spouses” when Decedent died on Date 1.

As the ruling noted, in this case the state’s ruling is binding on the IRS.

[1] http://www.ncsl.org/research/human-services/common-law-marriage.aspx