I have a Certificate of Marriage issued from NYC signed by the city clerk
How do I get it apostilled? Do I mail it to the NYC county clerk or the Department of State? Does it need a letter of exemplification?
You do not need a letter of exemplification. As noted at the New York Department of State link link in Nate Eldredge's comment, that is needed for birth and death certificates only.
The sheet of paper I mentioned in a comment has the same information as may be found under "fees" at https://www.cityclerk.nyc.gov/content/marriage-records. Essentially, you need a long-form certificate, which costs $35 instead of $15, and you must first visit the county clerk (to authenticate the city clerk's signature, for a fee of $3) and then the Department of State at 123 William Street (19th Floor) (for the apostille, which costs $10).