From the Super Mario Wiki
Super Mario World 2: Yoshi's Island / Yoshi's Island: Super Mario Advance 3
Stilt Guys first appeared in Super Mario World 2: Yoshi's Island. The sixth level in World 1 is named after them and shows off many different colored versions. If they are jumped on, they lose their stilts, leaving them no choice but to walk with their feet. Yoshi can lick them but it will only bump them backwards. Bumping them into water will cause them to sink, but if the water is shallow they will slowly emerge on the shore.
Stilt Guys also appeared in Yoshi's Story. Like in Super Mario World 2: Yoshi's Island, Yoshi had to land on their heads to make them fall off their stilts, leaving them no choice once again.
Yoshi's Island DS
The Stilt Guys' most recent appearance is in Yoshi's Island DS, along with Big Guy the Stilted, a giant, mechanical Stilt Guy boss. This game also introduces Stilts as an item that Yoshi can use for himself.
Paper Mario Stats and Tattle Information
Names in other languages