keyword searching

Hello, I am selecting a field in a database called description for keyword searching. The field contains names of people, states, years, etc. When someone searches for say "holmes north carolina" the query searches for exactly that, fields which have "holmes north carolina", and not fields that contaim holmes, north, and carolina. So I run a str_replace to replace all spaces with *, which turns it into "holmes*north*carolina", but say that north carolina is before holmes in the field, it won't return those fields (it only returns fields in which holmes is infront of north carolina). So how can I have it return all fields which contain all the words holmes, north, and carolina in any order, in that field?