From the Super Mario Wiki
Ads keep the MarioWiki independent and free :)
Mayor Penguin is the mayor of Shiver City. Like most of the city's inhabitants, he is a Bumpty. Mario first met the mayor at the party at Peach's castle before the events of Paper Mario began. The mayor was one of the few lucky guests to escape the castle's hijacking. Soon after these events, he returned safely to Shiver City.
When Mario was attempting to leave Shiver City to get to Starborn Valley, he learned that he had to get the mayor's permission to leave. While searching for the mayor, Mario found him lying on the floor of his room, unmoving. The Mayor's Wife then entered the room, and seeing her husband in this condition, believed him to be dead and accused Mario of murdering him. A nearby officer, hearing the disturbance, decided to investigate. After hearing the story, he decided to give Mario a chance to prove his innocence by finding the true killer. Going by the only scrap of evidence he found, a paper that the Mayor was clutching with the word Herringway written on it, Mario went out to prove his innocence. Finding Herringway the author, Mario convinced him to go to the mayor's house where Herringway was accused of killing the mayor. While the Penguin Patrol was placing Herringway under arrest, the Mayor suddenly sprung to life having only been unconscious the whole time. The Mayor explained that he had only fallen and knocked himself out while getting a gift for Herringway, with this explanation both Herringway and Mario were free to go.
Mario later had to go back to Shiver City and get a Bucket from the Mayor to gain access to Shiver Mountain. There's a letter for him in a tree at Shiver Snowfield. When Mario and Parakarry delivers it to him, he rewards Mario with a Star Piece.
While searching for the penguin that murdered the mayor, an alternate song is played in place of the normal Shiver City theme. This is the only time this song can be heard in the game.