Halifax – New York by train via Montreal
32 hours and 5 minutes, all the way by train. This is likely the most comfortable option, in particular if you book accommodation on the train. It's probably the more expensive alternative.
Day 1
Via Rail operate the Ocean from Halifax to Montreal, departing 12:30 on Tuesday, Friday, Sunday, arriving at Montreal at 8:29 the next day.
Day 2
The Adirondack departs Montreal 9:30 daily, arriving at New York at 20:35.
Halifax – New York by bus via Woodstock, Houlton, shortest route
32 hours and 55 minutes, by bus, taxi, and train. Probably the cheapest option.
If you take a 16 mi / 26 km taxi ride from Woodstock to Houlton, the journey is 703 mi / 1132 km. The alternative via Montreal is 1088 mi / 1751 km, so you cut off almost 400 mi / more than 600 km with a short taxi ride. I haven't checked the exact prices, but this is likely the cheapest option, depending on the accomodation you select for the night in Houlton.
Day 1
Maritime Bus can get you to Woodstock, NB, Canada:
Route map for Maritime Bus. Source.
Either 7:05 – 15:25 or 12:00 – 20:55.
From here, it's 16 mi / 26 km to Houlton, ME, USA: 12 mi / 19 km on the Canadian side, 4 mi / 7 km on the US side.
Day 2
From Houlton, ME, USA, travel by CYR from Houlton to Bangor, 8:20 – 11:10. See bus schedule: 1, 2.
From Bangor, Greyhound Lines has a bus line to Boston, 11:30 – 17:00, via Augusta and Portland. It passes through Portland at 14:45, so you might consider changing from bus t otrain there. Unfortunately, Amtrak Downeaster departs Portland at 14:35, so this connection fails, and wouldn't gain any time, as the Downeaster arrives Boston 17:05.
From Boston, connect to New York either by train or by bus. For example, the Acela Express departs 17:20 and arrives 20:55. If you miss this train, there are still trains at 18:45 and 21:30.
I don't know about the specifics of international taxi crossings; you may have to take a taxi to the border, pass the border, and take another taxi on the other side. Should be of interest for a question of its own.