Seen throughout the series run, Paul (played by Paul Willson) would generally hang around with Norm and Cliff in the hopes of being included in their activities. He appeared in more episodes than any other recurring character (55), with the exception of those who later were added to the main cast.
Paul was frequently not included with the rest of the group, something that upset him deeply. He was often treated like he didn't matter, had no friends, and was generally used and mistreated by the rest of the series characters. He did, however, have a certain amount of success with women, and was seen on dates in a few episodes. In the final season, it was suggested in the episode "Is There a Doctor in the Howe?" that Paul may be gay, but in the episode "It's Lonely on the Top" (five episodes later) he has a passionate one night stand with Carla.
The character was first called Paul in season four. In his first appearance, in season 1, Coach calls Willson's character "Glenn" (confusingly, the credits identify the character as "Gregg"), and in another early appearance, Willson is credited as "Tom", although this name is not spoken aloud in the episode. Towards the end of the series' run, a reference by Paul that he's been drinking at Cheers for 10 years makes it plausible that Coach misremembered his name in his first appearance 10 years prior, and that "Glenn" and Paul are meant to be one and the same person.
In the Season 10 episode "The Norm Who Came to Dinner", Norm explains that Paul (years earlier) had been an athlete who had been brought into the bar to try to get he and Cliff into shape, implying that Paul instead conformed to become the frumpy, smoking bar patron we see throughout the show's run.