From the Super Mario Wiki
A Recovery Block (also known as a Heart Block) is a type of block in Paper Mario. They are transparent blocks with a heart floating in the middle of the block. There are multiple different ones scattered throughout the game, each one refilling all of Mario's HP and FP when hit.
Recovery Blocks return in Paper Mario: The Thousand-Year Door, only now, it costs Mario a few coins for the health benefit, indicated above the block. The amount of coins required increases as one progresses through the game. Their design is very similar to that of their design in Paper Mario. 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. They function the same way as they do in Paper Mario, allowing Mario to use them at any time for free.
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. They are yellow with a heart in the middle of the block. 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. Their design in this game is that of a blue block with a heart symbol in the middle of the block. 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.