Fare un motore serio (con AND, OR, apici, etc) é un'altra cosa, però così da già dei buoni risultati, io faccio così:

codice:
$strArr = explode(" ", $stringa);

$qry = "SELECT * FROM tabella WHERE 1";
foreach ($strArr as $parola)
    $qry .= " AND titolo LIKE '%" . mysql_escape_string($parola) . "%'";