uf, hay miles de maneras
pero podrias hacer un select asi
Código:
<select name="tipo_busqueda">
<option value="apellido_paterno">Apellido materno</option>
<option value="apellido_materno">Apellido materno</option>
</select>
con un input asi
Código:
<input type="text" name="busqueda">
entonces la consulta podria ser
Código:
select * from mitabla where $tipo_busqueda=$busqueda
OJO! tiene miles de errores y no se valida nada, es solo un mero ejemplo :)
espero que te sirva saludos! :D