From the Super Mario Wiki
An Ultra Shroom is an item found in the Paper Mario series. This special mushroom has the same green cap as 1-Up Mushrooms (which are not found in the Paper Mario games, except Paper Mario: Sticker Star).
Ultra Shrooms are found randomly throughout the Mushroom Kingdom in the first Paper Mario. Occasionally, an Amazee Dayzee will drop an Ultra Shroom when defeated in battle. Very few places sell Ultra Shrooms: in Paper Mario: The Thousand-Year Door, they can be purchased for 200 Coins each at the Deepdown Depot, the shop in Rogueport Sewers, and they can also be found in the Pianta Parlor for 67 Pianta Tokens.
In Super Paper Mario, Ultra Shrooms are found hidden within ? Blocks. Due to their high HP recovery, they are generally found before boss battles during the later chapters of the game. They heal 50 HP on contact with the player, and their carry-on equivalent is the Ultra Shroom Shake.