I would like to present the same evidence as DavePhD's answer, but with a different summary of what it indicates.
In summary:
- NYC recognises 3 genders on Birth Certificates (M, F, and X)
- The number 31 probably comes from a list of gender-related terms which are not "legally recognised genders"
- There may be contexts where more than 3 options are recognised for "gender", but there is no evidence for a number as high as 31
A possible source for the "31 genders" claim is a leaflet published by the New York City Commission on Human Rights, dated 2015. One page (perhaps intended as one side of a double-sided card) starts with the text:
In New York City, it’s illegal to discriminate on the basis of gender identity and gender expression in the workplace, in public spaces, and in housing.
It goes on to give definitions of the terms "Gender Identity" and "Gender Expression", as well as listing some specific rights, and tips labelled "Courtesy 101".
The second page (perhaps intended as the other side of the card) consists simply of a list of 31 terms, with no title, and in no apparent order:
BI-GENDERED • CROSS-DRESSER • DRAG KING • DRAG QUEEN
FEMME QUEEN • FEMALE-TO-MALE • FTM • GENDER BENDER
GENDERQUEER • MALE-TO-FEMALE • MTF • NON-OP • HIJRA
PANGENDER • TRANSEXUAL/TRANSSEXUAL • TRANS PERSON
WOMAN • MAN • BUTCH • TWO-SPIRIT • TRANS • AGENDER
THIRD SEX • GENDER FLUID • NON-BINARY TRANSGENDER
ANDROGYNE • GENDER GIFTED • GENDER BLENDER • FEMME
PERSON OF TRANSGENDER EXPERIENCE • ANDROGYNOUS
The card does not state that these are "genders", or that they have any officially recognised meaning. Given the context of the card, we can assume they are intended as related to "Gender Identity" and "Gender Expression" in some way, but there is no other indication of why these particular terms were chosen.
It's also worth noting that the list includes clear synonyms, such as both "female-to-male" and its abbreviation "FTM"; it would be very surprising to find these recognised as distinct "genders".
Similar lists of terms can be found in other publications issued by the same authority, such as New York City Commission on Human Rights Legal Enforcement Guidance on Discrimination on the Basis of Gender Identity or Expression: Local Law No. 3 (2002); N.Y.C. Admin. Code § 8-102(23) which includes a "definitions" section.
An introductory paragraph describes the intent of the definitions:
These definitions are intended to help people understand the following guidance as well as their rights and responsibilities under the NYCHRL.
It includes a definition of "Gender" as an abstract term, rather than a countable one, and definitely doesn't enumerate any possibilities:
"Gender" includes actual or perceived sex, gender identity, and gender expression including a person's actual or perceived gender-related self-image, appearance, behavior, expression, or other gender-related characteristic, regardless of the sex assigned to that person at birth.
Other sections include examples, such as:
Terms associated with gender expression include, but are not limited to, androgynous, butch, female/woman/feminine, femme, gender non-conforming, male/man/masculine, or non-binary.
and
Terms associated with gender identity include, but are not limited to, agender, bigender, butch, female/woman/feminine, female to male (FTM), femme, gender diverse, gender fluid, gender queer, male/man/masculine, male to female (MTF), man of trans experience, pangender, or woman of trans experience.
These lists do not match the idea that "New York City legally recognises 31 different genders" for several reasons:
- They appear under multiple different terms in a glossary, so clearly are not all alternative types of the same thing.
- They are nowhere described as "different genders" or even "different gender identities"/"different gender expressions", only "terms associated with..." the concepts being defined.
- The text repeatedly reminds the reader that these are examples, not exhaustive lists.
This is made even more explicit in the introduction:
Readers should bear in mind that language evolves, and the best practice is to refer to people with the term(s) they use to self-identify.
One claim we could make from this document would therefore be "New York City legally recognises any terms people use to self-identify their gender identity and gender expression". However, it would be wrong to call those terms "different genders", and it would be wrong to give any specific number of possibilities.
There is one sentence in the definition of Gender Identity which could be said to "recognise" four distinct categories:
A person’s gender identity may be male, female, neither or both, i.e., non-binary or genderqueer.
I presume the author used "i.e." where "e.g." would be more appropriate, and "non-binary or genderqueer" are again just examples of things that fit into these categories.
It's not clear that these four categories have any specific definition or power in law; for instance, there is no indication that "neither" and "both" should be separate options on forms or identification documents. Again, the context we have to work in is that this is an explanatory guide to the concepts involved.
The alternative claim, that New York City legally recognizes exactly 3 genders on birth certificates, is true. A press release date 31st December 2018 announced the new policy:
The Health Department today announced that beginning Jan. 1, 2019, New Yorkers can change the gender on their birth certificate to "X" to reflect a non-binary gender identity.
This applies both to new birth registrations, and to amendments to existing certificates:
People born in New York City can submit a notarized affidavit that attests the gender marker change is to affirm their gender identity.
These are processed as "corrections" to the official record using an application form which confirms there are exactly three options:
I, [Applicant/Registrant], hereby attest under the penalty of perjury that the request to change the gender marker on my birth certificate no. [___],from [M/F/X] to [M/F/X], is to reflect my true gender identity and is not for any fraudulent purpose.
There is no mention in the press release of any fourth, fifth, or thirty-first gender options.