Check out How Would You Move Mt Fuji: Microsoft's Cult of the Puzzle it explains some of the common types of puzzles in use and the best ways to approach problems like that. Also explains about the background of these types of puzzle and why HR people like to use them.
Basically, they test your ability to think laterally rather than give up on what appears to be an impossible situation. This means questioning initial assumptions, thinking about information in an abstract way, breaking a problem down logically and then explaining your reasoning. The key thing to remember is that there usually is a way to solve the puzzle correctly; if there isn't - like the Mt Fuji example or the "How many piano tuners are there in the world.." - then they are just curious about how you would logically approach the problem anyway. Put yourself in the hypothetical situation. Where do you start, what can you base your estimation on?
If the puzzle does have a correct answer, you have been given all the information you need to solve it. Think carefully about the wording of the puzzle and how you might extract information from the particular scenario you have been given - if Mt Fuji, for example, why that mountain in particular? What is distinguishing about that mountain that could make it easier or harder to estimate how you would move it? Where could you move it to, and how long would that take?
There are a number of sites around that try to compile lists of the puzzles asked by Microsoft that you could find by Googling or someone will paste the links. If I was interviewing for Microsoft I would definitely want to study those questions.