I have done some plinking at Pouchuck Mountain its a NYSDEC state forest. I've talked to the ranger there and they have no problem with shooting there as long as you clean up after yourself, but its close to work not where I live.
I just got off the phone with NYSDEC about Stewart Forest which has some restrictions on guns and such. They informed me of the same thing that you can target shoot with airguns at Stewart as long as you clean up after yourself. Basically carry in and carry out. And for those that are interested you can hunt small game at Stewart with airguns too.