As mentioned, in Harriman/Bear mountain you are supposed to only camp in or near the shelters. That said, stealth (and exceedingly not so stealth) camping is common practice. Given its proximity to the NY metro area, the "backcountry" is surprisingly peaceful, especially this time of year. I backpacked the Ramapo-Dunderberg a couple of weeks ago and and only ran into a handful of people on a beautiful weekend. A huge portion of the hiker traffic is centered around the visitors center on 7 Lakes Drive. Let them have Pine Meadow Lake, we'll wander around the rest.
The place gets a bit of a bum rap, but there is a lot to like: loads of trails for near endless loop possibilities-all of which are maintained entirely by volunteers from the NYNJTC, home to the first section of the AT, lots of history, even George Washington has been hiking here. Coyote, bear, fox, plenty of deer, timber rattlers, black racers are really common. I've seen bald eagles and red-tailed hawks, and see vultures soaring overhead on nearly every visit. Blueberries galore in season, some really nice hemlock groves, a few scrambly talus slopes, hundreds of glacial erratics, loads of mountain laurel, a largely deciduous forest that puts on a nice autumn show and over thirty lakes. That is all a bit more than you were asking for, but I was up there this weekend for a short hike, and was thinking about how much time I spend up there and how much I like the place. Nothing epic, just a really pleasant forest.
Catkills: you can camp anywhere you want as long as you are: 150 feet from a body of water, a road, or a trail and below 3500 feet. In winter you can camp above 3500 feet, but no fires unless it's an emergency. There are also a lot of designated backcountry sites where the above rules don't apply; IE, you can camp five feet off the trail on a lake shore if there is a little yellow "camp here" disc. The Adirondack regs are pretty much the same, and you need a bear can in the eastern high peaks wilderness. BearVault won't do, we breed 'em smart over here.http://www.nytimes.com/2009/07/25/nyregion/25bear.html
No permits required unless you're in a group of 10 or plan on spending 3 nights in the same place. There are a few placed where you have to pay for parking.
That link will get you started on some public transportationable trips in the area.