I am a Canadian citizen working in the U.S. on a TN visa. I am changing my job (employer). Would I need to reenter the U.S. on a new TN visa? There is a gap between the end date of my previous job and the start date of my next job. Would I have to leave the U.S. during this gap?
When you leave the employer for which you got your current TN status, that status disappears and you need to apply for a new TN for the new employer.
I don't believe you absolutely need to leave the US to apply for the new TN, I think you could instead file for an I-129 change of status (from TN to TN) while remaining in the US. The downsides of doing it this way are that the I-129 application fee is $325 and it will take god-knows-how-long for them to process the application so you can go to work, while if you take a trip to the border it only costs $50 and you'll be done in 45 minutes. When I compared these options when changing jobs I always ended up travelling to the border, though I did get the company to file the I-129 for an extension.
If you do opt for the border trip there is the question of what status (if any) you have in the US once you've left your previous job (and TN) but before you get the new TN. If your current I-94 expires during the gap you certainly want to leave by that date. Otherwise, one of the CBP officers who processed my TN told me I had 30 days to leave the US if I left my job, and while I know of no authoritative source for that number I certainly don't think you should wait any longer than that to travel to the border if you decide to do it that way.