From the Super Mario Wiki
In Paper Mario, the Postmaster can be found behind a desk in the Post Office; if Mario talks to him, the Postmaster will let Mario read various letters sent to his partners by various people and organizations they've met in their travels.
When Shy Guys began to cause havoc in Toad Town, the Postmaster had a bag of mail stolen from him by a Shy Guy. If Mario found this mail bag and the letters it held, he could give it back to the Postmaster and receive a Star Piece as a reward.
When Mario returns to Toad Town after his adventures on Lavalava Island, a Toad in the town will mention the Postmaster. The Toad will go on to recount that while he was eating lunch at Club 64 with him, the Postmaster said he was worried about Parakarry's slowness in delivering mail. However, as the Postmaster said this, he was smiling, which the Toad took to mean that the Postmaster was secretly proud of having found a successor.
"This Paratroopa looks extremely serious. And stubborn. And hardheaded. If you have a letter coming, he'll give it to you. I wonder if he has one for me."