This expression typically alludes to verbal praise, but it could be extended to other tangible ways of recognizing a job well done.
Let's say that Joe works for Paul, and Joe has been doing a good job. (Perhaps he's done a good job for the past year, or maybe he's been working on a special project for a few weeks.) Either way, Paul wants to formally recognize Joe's acheivements, that is, he wants to give Joe a figurative pat on the back.
He could do this in a number of ways: he could thank Joe privately, or he could offer his kudos publicly. He could give Joe a day off, or a small bonus. He might even give Joe a raise, or recommend him for a promotion. Any of these could be ways to give Joe a pat on the back, that is, to recognize and acknowledge Joe's acheivements, and thank or praise him for those accomplishments.
Someone might want to be recognized for his own good work, too, and give himself a pat on the back. That expression is often used sardonically, though, in response to someone who is perhaps bragging too much:
Dwight: Last month, I had more sales than anyone else in the office.
Jim: Well, you should give yourself a pat on the back, then!
When used in this context, there's a certain deliberate awkwardness to it, because it's much more difficult to put your hand literally on your own back than on someone else's.