After 30 minutes May kicked his third penalty from just outside the 22 to leave the Falcons leading 16-3 at half-time.
Bristol started the second period strongly, but the visitors regained their grip on the game when open-side flanker Williamson broke down the right touchline to score their second try.
Replacement number eight Brent Wilson finished off a fine blind-side move down the wing before May added the conversion.
And with less than 10 minutes left the Falcons secured a bonus-point try through replacement lock Perry, with May adding the conversion.
Bristol head coach Richard Hill:
Newcastle 'blew us away' - Hill
"There were not many points to take from this game but it is not the end of the world.
"It is not curtains for our season but we will now have to focus on beating Worcester as Newcastle are probably out of reach. It is not over but we will have to change our focus.
"I can't explain a 35-point hammering. We shouldn't lose by that much on our ground. It was a big game and there is no hiding from that but at the moment I don't know why we put in that performance.
"I know Newcastle played exceptionally well but canvassing our players after the game as to what happened and why it did happen, nobody could put their finger on it.
"The defeat is going to hurt but we have to pick ourselves up and target Worcester as well as picking up as many points as we can. But it will be tough as we are all wondering why this happened tonight."
Newcastle Falcons coach Steve Bates:
Hard work reaps rewards for Falcons
"I think we need to think positively and say why don't we look at getting in to mid-table.
"There is another nine games to go and we should say that we are capable of being right up there and perhaps aim for seventh place.
"I thought that the guys played really well and deserved the victory.
"Defensively we were pretty strong and I thought that when we came in at half-time that we could have been further ahead than we were.
"We started well which was important because we knew that they would be hungry because it was a massive game for them and we had to make sure that we didn't give them anything to fuel that enthusiasm."
Bristol: T. Arscott, Robinson, N. Brew, N. Brew, Lemi, Barnes, Perry, Irish, Regan, Crompton, Winters, Budgett, Salter, To'oala, Ward-Smith.
Replacements: Eves for N. Brew (67), Jarvis for Barnes (54), Beveridge for Perry (70), Blaney for Regan (61), Thompson for Crompton (67), Attwood for Winters (67), El Abd for Salter (50).
Newcastle: Tait, D. Williams, Noon, Tu'ipulotu, Rudd, May, Young, D. Wilson, Vickers, Hayman, Swinson, Parling, Dowson, Williamson, Balding.
Replacements: Davey for Noon (76), Clegg for May (76), Charlton for Young (70), Golding for D. Wilson (65), Perry for Swinson (70), B. Wilson for Balding (57).
Bookmark with:
What are these?