Yes, my apologies, I forgot the percent signs! Big typo on my part and I hope I didn't waste your time. vincent has a good point about the indices though.
I'm sure vincent will have a better idea, but to get you started you can do something akin to:
$keyword = strToLower("New");
SELECT *
FROM tablename
WHERE LCASE(City) LIKE '%$keyword%'
OR LCASE(State) LIKE '%$keyword%'
OR LCASE(Zip) LIKE '%$keyword%'
You can get MUCH fancier than that, especially in your ORDER BY clause, but that should at least get you matching rows.