Information Literacy education is challenged by an ever-changing and complex environment. The design and development of current and effective Information Literacy education requires a thorough understanding of how young people search information online, which mainly happens with generalist search engines. The present study involved a voluntary sample of 152 young people (age group 16-20), who were asked to solve four different information tasks. We collected 595 search stories, each containing the sequence of navigation actions performed while solving a single information task, enriched with automatic metadata. We used cluster analysis to identify emergent search behaviors, and statistical analysis to observe behavior variation and to connect emergent behaviors with performance. Visual plots were developed to make search stories inspectable by humans and also usable as instructional tools. Young people demonstrate a variety of identifiable search behaviors that differ in use of time, use of search keywords, and overall search story structure. Subjects with less elaborated search stories (about 60% of the sample) tend to be less flexible in adapting their search behavior to the task and the situation. Such heterogeneity should be considered for reinterpreting traditional Information Literacy instructional models and tools, and a starting point in the design of effective online search education lessons up to the challenges of our times.