I did much of your intended route in July/August 2001. I was going to cycle from Ottawa to Washington (capital to capital), but I stopped in Philadelphia because of a killer heatwave and a plunging Canadian dollar (went down to 62 cents that summer) which made things ridiculously expensive for me, especially in the urban areas. I ended up taking the train to Boston and riding up the cooler, rustic northeast and ended my tour in Halifax, Nova Scotia.
Cycling through the Adirondacks is really nice, with lots of opportunities to free camp. Parts of the Hudson Valley are a quite industrialized, and you'll be passing though some tight spots once in a while, especially around Albany. There is a nice paved rail trail between Glens Falls and Lake George, make sure you find it.
I chose to cycle along the Jersey Shore between Highlands and Tom's River. There's a ferry
that runs between Manhattan and Highlands which allows you to skip the mess of endless Newark/Jersey city suburbs. I imagine going the other way, it would be a spectacularly scenic way to enter NYC, sailing through the Verrazano Narrows and past the statue of Liberty. Manhattan is surprisingly cycleable, the biggest problem is securing your bike if you want to see the sights. The best way to get out of Manhattan from the north is the George Washington Bridge which has a cycleable path on its south side. From there you are clear into the Pallisades and the Hudson Valley.
There was a fierce headwind for me on the Jersey shore, but it should be great for you if you are heading north. I saw a few road cyclists in the Pine Barrens between Tom's River and Philadelphia which seems to be a training run for people in the area. One thing about this region is that there are very few established campgrounds, and free camping is really difficult along the some stretches.
BTW, you should consider coming up to Ottawa, less than 200 kms east of Montreal. The route would take you over the dome of the Adirondacks into the heart of the park and Lake Placid which has hosted the Winter Olympics twice. The Canadian capital has close ties with Holland (it is twinned with The Hague) as the Dutch Royal Family was exiled here during World War II (Princess Margriet
was born in Ottawa). From here to Montreal is an easy cycle along the Ottawa River. I gladly host touring cyclists at my place on warmshowers.org, so let me know if you decide to pass by.
Best of luck, you are doing the right thing going from south to north, the wind will mostly be on your back.