Recently the New York State Death Index (1880-1956) was made available online for free. The organization, Reclaim the Records, a not-for-profit group of genealogists, historians, and government advocates who file Freedom of Information (FoI) requests to have public data released into public domain won its case that this index should be made available as free public records.
However the index does not include all municipalities in New York State. For example the City of Albany is not included in this index; most unfortunate for local researchers! The index is broken down alphabetically by year on the the site.