In both the Underground map example and the jigsaw puzzle, we showed how a program could explore a set of possibilities by developing possible paths towards a goal. Each node in a tree represented some situation, in one case that of having arrived at a particular station, in the other that of having fitted certain pieces into the frame. These situations are known as states and the collection of all the possible states pertaining to a problem is called state-space. You can picture state-space as simply a table on which descriptions of all the states are laid out, waiting to be examined in turn. In many real problems the state-space, if it were really laid out like this, would be inconceivably huge, but the metaphor is often useful in thinking about what the program is trying to do.
In practice a program builds up its state space step by step. Note that in both the examples the trees were created by going down branches, to which new nodes were added by making one change from the node above. Such nodes represent neighbours in state-space. If a program were to try different states in state-space at random to see if they produced a solution, clearly it would be most unlikely to find one. Search strategies allow programs to cover state-space in a systematic way, jumping from a state to its neighbours, so as to organize an efficient search.