Also, the materials used to build the puppet should be fairly standard, readily available materials. If the character is to be a monster, probably a short nap fur in a common color should be used.
More importantly, though, what's the character's story? WHY is he traveling around the world? I think to just see the sites is a little weak. He should have a purpose, which could also serve as a basis for the plot of the video shorts. Is he searching for something? Chasing something or someone? There should be a central purpose to his existence.