Because many AI problems can be readily modeled as state spaces, and solving these problems can "simply" be reduced to exploring the state space, and identifying the correct answer. That is search and is essentially what programs like Deep Blue do. Modeling and solving problems on a computer in this manner dates back to Alan Turing.
Incidentally, this type of search isn't the same as searching for a keyword in a database. This isn't the kind of search google does. The state-space of AI problems is usually extremely large, and can't even be fully stored in a computer's memory or hard disk. Worse, it would take the lifetime of the universe and then some to explore fully. That is why I put "simply" in quotes. The clever bit around search in AI involves examining these state spaces efficiently. Not all that simple.