From Gettysburg, get on 81 and take that to 84 to the Mass Pike. That'll avoid NYC. In Boston you could stay in Foxboro, MA at Normandy Farms. From there take 495 around Boston to 95. Take that to Bangor and then go over to Bar Harbor. From Bar Harbor to New Brunswick I'd take either 9 or 1. 9 may be faster and 1 may be more scenic.
To get to New Brunswick you need to take the ferry out of Sydney. I'd take the short ferry to the Rock. From Newfoundland there is another ferry to Labrador. When we were there the paved roads ended not too long after getting to Labrador so we didn't go any further. Others might help on Labrador (except bring insect repellent).
