Picking the right materials is important and probably easier for the physical prototype (paper, card, clay), but can be a little trickier for software. Check out this great interactive matrix of tools here, which can help you pick a suitable tool. I have seen simple animated white board drawings used effectively. Quick note on reuse - do not get caught up trying to reuse prototype code in the real product, and you should only reuse it between prototypes if it helps you produce prototypes faster. Don't fall into the trap of going deep either; otherwise you are at risk of building the end to end system.
Tom advocated giving the prototype team rate based goals*. Why? It encourages producing many designs quickly which increases the chances of success. The probability of finding the right solution increases as you try more ideas out – ‘suppose your success rate is 5% of time and you try 20 things / ideas then the chance of success is 64%, try 50 times then there is a 92% chance of success’. Trying eliminates the guess work, ‘try don’t guess’ because ‘trying is not failing as long as you are learning something, so look for what worked in each prototype and then discard what didn’t’. The more you understand the problem space the better the product. When you don’t have hard data upon which to base your decisions, often the case when you are building new products, trying ideas out helps prevent building HiPPO products.
*Rate based goals may seem contrary to creativity, however it should not deter you from using them - it is all about the number of ideas, good or bad it does not matter.