welcome to the addiction!
There is a complete menu of places to hang in NY.
Paid private campsites, paid public campgrounds, drive-in free public campsites, free hike/paddle in public sites,... I am more familiar with the Central and Western Adirondacks and could give you specifics in those regions. I know the same exist in the South and Eastern portion of the Adks (and Catskills) if you know where to go. One place to start would be the NYS DEC website with all the public lands and their specific regulations. For example an (incomplete) list of State Forests is here: http://www.dec.ny.gov/lands/34531.html