this is a really worthwhile trip. Braganca is a lovely town, an ideal place to go after you finish your camino, too.. it´s where Spaniards go to buy Portuguese linens and towels and matellassé quilts! It is just over the river from Tui, in Spain. Which puts you onto the Portuguese camino! (there are pilgrim hostels along here.)
The terrain you describe is indeed hilly, with some rolling country and some pretty steep descents and climbs, especially as you near the river valleys. There is much to see in this little area, with history and remains and ruins reaching back to prehistory. Once you hit the larger towns there is plenty of accommodation, but the space between? That is where my helpfulness peters out and I refer you back to Alison for details, she Knows All where caminos are concerned. I nosed around the Braganca/Verin/Vigo area two summers ago, and really fell for it. But I was not on foot, and I had a native to show me around.
Verin is popular with Portugese pilgrims, especially bikers. It too is a wonderfully historic and strategic place, with a hilltop with no less than THREE castles on top, as well as a monastery...and a pilgrim hostel! This part of the trip is downright mountainous, and it´s well touristed. You shouldn´t have trouble finding places to stay, long as you don´t expect it to be in the 3-Euros-to free category. You may find the info you need on these areas in guides to the Portuguese camino.
Have a great time out there!
Rebekah