People working together can be very successful problem-solvers. Many real-life examples, from Wikipedia to citizen science projects, show that, under the right conditions, crowds can find remarkable solutions to complex problems. Yet, joining the capabilities of many people can be challenging. What factors make some groups more successful than others? How does the nature of the problem and the structure of the environment influence the group's performance? To answer these questions, I consider problem-solving as a search process -- a situation in which individuals are searching for a good solution. I describe and compare three different methods for structuring groups: (1) non-interacting groups, where individuals search independently without exchanging any information, (2) social groups, where individuals freely exchange information during their search, and (3) solution-influenced groups, where individuals repeatedly contribute to a shared collective solution. First, I introduce the idea of transmission chains - a specific type of solution-influenced group where individuals tackle the problem one after another, each one starting from the solution of its predecessor. I apply this method to binary choice problems and compare it to majority voting rules in non-interacting groups. The results show that transmission chains are superior in environments where individual accuracy is low and confidence is a reliable indicator of performance. This type of environment, however, is rarely observed in two experimental datasets. Then, I evaluate the performance of transmission chains for problems that have a complex structure, such as multidimensional optimization tasks. Again, I use non-interacting groups as a comparison, this time by selecting the best out of multiple independent solutions. Simulations and experimental data show that transmission chains outperform independent groups under two environmental conditions: either when problems are rather easy, or when group members are relatively unskilled. Next, I focus on social groups, where individuals influence each other during the search. To understand the social dynamics that operate in such groups, I conduct two studies: I first examine how people search for a solution independently from others, and then study how this individual process is impacted by social influence. The first study presents experimental data to show that the individual search behavior can be described by a take-the-best heuristic, that is, a simple rule-of-thumb that ignores all but one cue at a time. This heuristic reproduces a variety of behavioral patterns observed in different environments. Then, I extend this heuristic to include social interactions where multiple individuals exchange information during their search. My results show that, in this case, individuals tend to converge towards similar solutions. This induces a collective search dilemma: compared to non-interacting groups, the quality of the average individual's solution is improved at the expense of the best solution of the group. Nevertheless, further analyses show that this dilemma disappears for more difficult problems. Overall, this thesis shows that no collective problem-solving method is superior to the others in all environments and for all problems. Instead, the performance of each method depends on numerous factors, such as the nature of the task, the problem difficulty, the group composition, and the skill levels of the individuals. My work helps understanding the role of these different factors and their influence on collective problem-solving.