From the Super Mario Wiki
A Recovery Block (also known as a Heart Block) is a type of block in Paper Mario. There are multiple different ones scattered throughout the game, each one refilling all of Mario's HP and FP. The first block is found in Jr. Troopa's Playground near Goomba Road, where the game gives a description about the blocks.
Recovery Blocks returned in Paper Mario: The Thousand-Year Door, only now, it would cost Mario a few coins for the health benefit, indicated above the block. The amount of coins required increases as one progresses through the game. This same concept is used with the Inn's pricing as well. The first block is found at Shhwonk Fortress, where it again gives a brief description about the blocks. These blocks are usually, if not always, found right before a boss fight, and right when Mario enters a new area such as Mt. Rugged or Hooktail's Castle.
Recovery Blocks reappear in Paper Mario: Sticker Star. Like with Paper Mario, they are free to use and may be used again immediately after one use.
In the Japanese version of Mario & Luigi: Superstar Saga, a similar block that heals all of the brothers' HP and Bros. Points appears in three locations; the Beanbean Castle Sewers, Oho Oasis, and Teehee Valley. However, these are not present in any of the other regional releases for unknown reasons.
A few Recovery Blocks are found in Mario & Luigi: Partners in Time, though they are scarce. There is one in Princess Peach's Castle in the present, one inside of the monstrous Yoob, and one just before the throne room of Shroob Castle. As in Paper Mario, they are free to use.