Super Blocks are blocks that contain a spinning blue disk in Paper Mario. Much like Merlon in Paper Mario: The Thousand-Year Door, the Super Block upgrades Mario's partners. Unfortunately for Mario, the Blocks are scattered all across the Mushroom Kingdom.
Each of Mario's partners can be upgraded twice; the first time to a Super Rank and the second time to an Ultra Rank after Mario receives the Ultra Stone from Raphael the Raven in Chapter 5. However, even after Mario receives the Ultra Stone, he still can't choose to Ultra Rank a partner if everybody else isn't at Super Rank.
Oddly enough, in The Adventures of Super Mario Bros. 3 episode "Super Koopa", Mario referred to a standard Brick Block as a Super Block.