If your REGEXP string delimiters are single quotes, escape them within the string. Also, depending on your business logic and table structure, you could do a CONCAT to condense the statement:
SELECT field1, field2
WHERE CONCAT( field1, field2 ) REGEXP 'Mary\'s Restaurant'
If you're using a dash within a character class, either escape it or make it the first item in the class, so the engine doesn't think you're trying to specify a range:
... REGEXP 'Mary\'s[- _]Restaurant'
If you're using your San Diego example, you might be able to reduce the REGEXP by using word boundaries:
SELECT field1, field2
WHERE CONCAT( field1, field2 ) REGEXP '[[:<:]]SAN DIEGO[[:>:]]'
See: MySQL 5.1 REGEXP Manual