Problem-based learning (PBL) is an instructional approach that is organized around the investigation and resolution of problems. Problems are neither uniform nor similar. Jonassen (1997, 2000) in his design theory of problem solving has categorized problems into two broad types--well-structured and ill-structured. He has also described a host of mediating skills that impact problem solving outcomes. The thrust of this paper rests in the argument that the basis of these mediating skills is information search literacy and particularly, in view of the utility of the Internet as an informational repository, effective information searching skills. This study was an investigation of how different Internet information seeking strategies can be used to engage in problem solving. A conceptual framework that explains how different Internet information searching strategies can be employed in successfully solving well and ill-structured problems was devised and empirically tested. The research site was a newly established polytechnic in Singapore that employs problem-based learning to support its curricular implementation. The sample population of students came from a class of 25 first-year students. The research findings of this study inform that information searching skills indeed play an important role in problem solving. The findings affirm the need for students to be systematically instructed in the skills of information searching to be able to accomplish problem solving. The information searching necessary for solving well-structured problems is constrained and readily manageable. Thus, students only have to be acquainted with fundamental information searching skills to solve well-structured problems. On the other hand, the information needs of ill-structured problems are usually complex, multi-disciplinary and expansive. Hence, students have to be trained to apply a more advanced set of information searching skills in resolving ill-structured problems. (Contains 4 figures.)