You may identify the phrases based on the double quotes and then use the LIKE to run the queries. To exclude rows that contain words like -red the NOT LIKE could be used. REGEXP and NOT REGEXP can be used for more complex searches.

Now the search criteria needs to be parsed, so if it's not a whole phrase, to break down into words and then broaden the search. Simple example

$search_words = array();
$check_array = explode(' ', $search);
for($i=0, $j=count($check_array); $i<$j) {
$pos = strpos($check_array[$i], '-');
if( $pos !== false && !$pos ) continue; // skip exceptions
$search_words[] = "db_col LIKE '%" . $check_array[$i] . "%'";
}

$search_string = 'where ' . implode(' or ', $search_words);
$q = mysql_query("select db_col from products " . $search_string);

This may match parts of the word so you may have to modify the search afterwards using common prefix characters space, hyphens, comas etc
$search_words[] = "db_col LIKE '%-" . $check_array[$i] . "%'";
$search_words[] = "db_col LIKE '% " . $check_array[$i] . "%'";

There are other methods using the FULLTEXT match/against for instance and you may want to check the string manipulation functions your database supports as the code assumes mysql

So given a user-entered search term of `red fuzzy widgets` I would first run this query against the ad table:

SELECT * FROM `ads` WHERE `keywords` LIKE '%red%' OR `keywords` LIKE '%fuzzy%' OR `keywords` LIKE '%widgets%';

Then only check those specific keyword phrases against the user-entered search term? I can see that working for quite a few situations, but I can think of a few situations where it doesn't -- particularly stemming.

For example, if the keyword is "blue widget" and the user entered `blue widgets` then doing a LIKE '%widgets%' would *not* bring up the singular form in the table. :/

I think I'll go do some research into stemming algorithms.

There are certain ways to improve these simple search queries. For instance if we assume the majority of plural words end up in 's' or 'es' then if the first query fails you could initiate a second trimming words ending with these combinations of characters.

You could setup some sensitivity switches so when the query is executed again the chances increase to bring up results removing characters from the end and setting up a threshold to end the operation.
$check_array[$i] = substr($check_array[$i],0,-1);

As each word decreases in length, the chances to retrieve results increase and to compensate for the errors you could utilize functionality perhaps that has to do with pronouncing. In php, there are few like soundex, metaphone, similar_text etc. You could try converting the input words first through the soundex or when you retrieve results that may be inaccurate to filter them through the similar_text. Of course you will need to parse each resulting row again for this and can be intense.

Another thing you may want to do is to precede words in your query with expected separation characters so the results are more accurate.

SELECT * FROM `ads` WHERE `keywords` LIKE 'red%' OR `keywords` LIKE '% red%'......
because you expect 'red' to be at the beginning of a sentence or to be the beginning of a word (eg 'shredding' may also come up when searching for 'red'). For this kind of search you expect the beginning of the phrase to be more accurate than the end.

It seems to me though that this approach is computationally very expensive -- I'm practically comparing every row in the ads table against the search term in multiple ways. With some caching, I may be able to make this work when I have less than 1,000 ads, but how would it be handled with 100,000s of ads?

It doesn't matter even if it's a million. Because you will only need enough records to populate a page the user views right? So that will be couple of dozen records? So you setup an index/limit because when you present the results to the user you deploy pagination.