punchline you need to use php to construct a giant complex sql statement.. something like my example below could be extended to do something like you want (i think)
1) parse search box into array of AND strings and an array of OR strings... this could be a complex regeular expression of some kind...
2) step through each array to construct this sql statement below or something similar...
SELECT
*
FROM
TABLE
WHERE
(
/* AND partial word match */
column LIKE '%$word1%'
AND
column LIKE '%$word2%'
AND
column LIKE '%$word3%'
) OR (
/* OR partial word match */
column LIKE '%$word4%'
OR
column LIKE '%$word5%'
OR
column LIKE '%$word6%'
)