The Ultra Stone appears in Paper Mario as it is used by Merlon to promote Mario's partners to their Ultra Rank after they hit the Super Block. It can be obtained after Raphael the Raven in Jade Jungle makes the pulley so that Mario can gain access to the Mt. Lavalava.
It would return in Paper Mario: The Thousand-Year Door for the same reason as it was in Paper Mario. Merlon would forget that he owns the item and will only remember after he gets the Up Arrow after Mario gets that item from Hooktail Castle with the help of Admiral Bobbery. To upgrade his partners to Ultra Rank, Mario needs to give Merlon, three Shine Sprites.
Related ThreadsHow Do You Ultra-Rank Your Partners? - last post by @ Oct 20, 2004
How do you use ultra rank stone? - last post by @ Jan 4, 2003