Problem solving is the highest level of cognitive skills for thinking. However, this skill seems to be lacking among graduates from higher institutes of learning. In addition, there does not seem to be many instructional models for teachers to teach problem solving and little research on it in Malaysia. Early research on problem solving focused on the psychological processes, definitions and heuristics for solving problems and were limited to the individual in the attempt to make explicit the internalized processes. Studies on generalized problems were limited to solving problems in not much on teaching problem-solving strategies. The purpose of this paper is to discuss an approach for teaching problem solving in authentic and meaningful situations so that learners can acquire problem-solving skills to be successful at the workplace. In order to develop an overall strategy to solve the different types of problems, several principles of learning for teaching problem solving are discussed. Technology can support the existing models of problem solving. Further research is required to determine if these principles of learning can be applied to all problem types, in different subject matter, and to what extend teachers are applying these principles in their instruction in Malaysia. Models of instruction for problem-solving specific to the Malaysian context can be developed and evaluated for its suitability for teaching problem solving skills.