The Stack Exchange search is not very good, and has not been very good for a long time (though it has improved greatly). It's been discussed many times on Meta Stack Overflow and for reasons beyond my ken the powers that be are simply not interested in changing it appreciably. I presume they have good reason, as they've demonstrated many times in other areas their ability to think deeply and come up with good solutions to core issues.
The most popular workaround seems to be to use google and their site: syntax to restrict searching to a particular domain. Although effective I've never really liked that because of the extra friction of keeping an extra tab open just for that purpose, and it's too much extra typing.
As MatrixFrog suggests, a very effective and non-traditional method of "searching" is to "click on Ask Question and write out the full question (as though you had searched thoroughly and not found it). Then, look at the list of questions that comes up, under your question title. Maybe it's a different search algorithm, or maybe it just does better with full well-written titles than with keywords, but it seems to do a little better IME." -- however please don't actually post your question unless it truly is unique!
Today I discovered Google Custom Search. I think I like it, even though it does still mean having an extra tab open. Here's a GIS.se_custom_search which searches GIS.se and meta.GIS.se, and the code which you can plop into any web page for the same (though unfortunately not here on this site):
<div id="cse" style="width: 100%;">Loading</div>
<script src="http://www.google.com/jsapi" type="text/javascript"></script>
<script type="text/javascript">
google.load('search', '1', {language : 'en', style : google.loader.themes.SHINY});
google.setOnLoadCallback(function() {
var customSearchControl = new google.search.CustomSearchControl('003470880514237939557:dzuoqbegndm');
customSearchControl.setResultSetSize(google.search.Search.FILTERED_CSE_RESULTSET);
customSearchControl.draw('cse');
}, true);
</script>
