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.
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.
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.
Maritime Bus can get you to Woodstock, NB, Canada:
Route map for Maritime Bus. Source.
Either 7:15 – 15:15 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.
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.