Tente algo assim:
SELECT * FROM clients WHERE CONCAT(field1, '', field2, '', fieldn) LIKE "%Mary%"
Você pode querer ver documentos SQL para obter informações adicionais sobre operadores de string e expressões regulares.
Editar:pode haver alguns problemas com campos NULL, portanto, caso você queira usar
IFNULL(field_i, '') em vez de apenas field_i Sensibilidade a maiúsculas :Você pode usar o agrupamento que não diferencia maiúsculas de minúsculas ou algo assim:
... WHERE LOWER(CONCAT(...)) LIKE LOWER("%Mary%")
Basta pesquisar todos os campos :acredito que não há como fazer uma consulta SQL que pesquise em todos os campos sem declarar explicitamente o campo para pesquisar. A razão é que existe uma teoria de bancos de dados relacionais e regras estritas para manipular dados relacionais (algo como álgebra relacional ou codd álgebra; é daí que vem o SQL), e a teoria não permite coisas como "apenas pesquise todos os campos". É claro que o comportamento real depende da realização concreta do fornecedor. Mas no caso comum não é possível. Para ter certeza, marque
SELECT sintaxe do operador (WHERE seção, para ser preciso). 
