Why is search important in AI? Why is search important in AI? What kinds of search algorithms are used in AI? How do they improve the result of an 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.