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
Yoshi's New Island
The Stilt Guys' most recent appearance is in Yoshi's New Island. Just like in Super Mario World 2: Yoshi's Island, when they are on their stilts and Yoshi attempts to lick them they bump backwards. They need to be jumped on in order to be killed, just like in Yoshi's Story and in SMW2: Yoshi's Island.
Paper Mario stats and Tattle information
Names in other languages