Why is search important in AI?
State space search is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.

State space search is an abstraction which can be customized for a particular problem via three ingredients:


Some representation for candidate solutions to the problem (e.g. permutation of cities to represent a Travelling Salesman Problem (TSP) tour, vector of real values for numeric problems).
A solution quality measure: i.e. some means of deciding which of two solutions is the better. This is typically achieved (for single-objective problems) by having via some integer or real-valued function of a solution (e.g. total distance travelled for a TSP tour). 
Some means of moving around in the space of possible solutions, in a heuristically-informed manner. Derivatives can be used if available, or else (e.g. for black-box problems or discrete solution representations) the kind of mutation or crossover methods favoured by genetic algorithms/evolutionary computation can be employed.


The first couple of chapters of the freely available "Essentials of Metaheuristics" give an excellent overview and  Michalewicz and Fogel's "How to Solve It - Modern Heuristics" explains in more detail how numerical optimization can be considered in terms of state-space.

How shall the "search through possible plans" occur? The idea is to choose all 3 of the above for the planning problem and then apply some metaheuristic (such as Simulated Annealing, Tabu Search, Genetic Algorithms etc). Clearly, for nontrivial problems, only a small fraction of the space of "all possible plans" is actually explored.

CAVEAT: Actually planning (in contrast to the vast majority of other problems amenable to state-space search such as scheduling, packing, routing etc) is a bit of a special case, in that it is sometime possible to solve planning problems simply by using A* search, rather than searching with a stochastic metaheuristic.