I hunted in Newfoundland this fall. I took Lacrosse AlphaBurly boots and Kenetrek Mtn Extremes with gaiters. I wore the Kenetreks every day and was very happy to have the support and comfort.
Develop a good base level of aerobic fitness and you'll be fine - lunges, step-ups, and treadmill time at 12%.
We had some climbs of 600-900'+ from the lake in the morning, but much of it was a more rolling landscape with intermittent steep hills. Avoid walking through bogs or puddles - step where your guide steps or on light colored grass. Walking through the tuckamore can be really difficult, but we generally used existing game trails, which were much easier than bushwhacking. If you get winded, take a break, then get back to it.