The Ultra Stone is a Crystal Ball used by Merlon in Paper Mario. It lets Mario's partners advance to the Ultra Rank when they hit a Super Block. Mario receives it from Raphael the Raven in Jade Jungle after making a pulley to Mt. Lavalava. All of the party's members should be at Super Rank by then.
The Ultra Stone reappears in Paper Mario: The Thousand-Year Door. It is in the possession of Merlon. However, he forgot about its existence and was only reminded of it by the Up Arrow which Mario can find in Hooktail Castle with Admiral Bobbery's help. With the Ultra Stone, Merlon is able to upgrade Mario's partners to Ultra Rank, for the usual three Shine Sprites.