Problem-solving skills are often identified as a key component of 21st century education. This study collected data from students enrolled in a university-level Liberal Education science course called "Problems and Puzzles," which introduced students to the theory and practice of problem solving via puzzles. Based on classroom observation and other qualitative data collected over three semesters, we have identified three significant changes in student behaviour at specific points in the course. These changes can be posited to reveal three underlying threshold concepts in the evolution and establishment of students' problem-solving skills.