Indeed, PANB (Provincial Archives of New Brunswick) should definitely be the first stop for anyone with ancestors in New Brunswick. It's an amazing resource. I really wish other provinces would follow suit in the depth and breadth of information freely available. As well, I've contacted PANB a few times for information and they've been most helpful.
Here's a recent blog post that lists some other good New Brunswick resources:
http://familytreeknots.blogspot.ca/2015/07/new-brunswick-research-sites.html
As well, the Canadian census is a great tool. For New Brunswick, the Census starts in 1851. You can find all of the Canadian censuses for free on the Library and Archives Canada (LAC) site (
http://www.bac-lac.gc.ca/eng/census/Pages/census.aspx), except 1921, which is available for free on Ancestry.
Here's a tip for working with the Canadian census. The LAC site does not have a great search function - if you don't have the exact spelling on the index, you won't find the entry. Family Search has all of the indices, but not the images. What I do is search for the name I'm interested in on Family Search, get the exact spelling that was used, and then use that on the LAC site to get the image of the census page. Works like a charm! Alternatively you can find them on Ancestry, but if you don't have a paid subscription, the FamilySearch/LAC combo is a good solution.