The goody that you hope to find--a solution to a math problem, a great job, a great spouse, just the right synonym, an explanation of something, etc.--is out there. Somewhere. It's just buried among a lot of places to look.
The search space is the set of possible places to look, for whatever kind of goody you're trying to find.
In the case of finding a synonym, the Search Space is all words in your language. In the case of a great job, it's all the places you could look to find a job. In the case of finding an explanation, the Search Space is unimaginably large and irregular.
A heuristic is a way to navigate a Search Space.
Most heuristics work by reducing the size of the Search Space, or giving you a way to move from one place to the next within a Search Space, e.g. Hill Climbing. Some work by enlarging it. For example, trying to find a job by sending out resumes is usually fruitless. If you talk to your friends and ask them to ask around, you greatly enlarge your set of possible ways to make a connection, and the connections you find that way are usually better.
See also: Yawning Void.