Una forma muy sencilla sería, como bien dices, utilizar la función explode():
 http://www.php.net/manual/es/function.explode.php 
El objetivo es poder construir un sql algo así:
 Código PHP:
    $sql = "SELECT * FROM producto.allista WHERE busqueda LIKE %p1% OR busqueda LIKE %p2% OR busqueda LIKE %p3%"; 
    
  Te voy a poner un ejemplo de cómo conseguir esto: 
 Código PHP:
    //Suponiendo que las palabras por buscar están separadas por un signo "+":
 
if(!empty($_GET['criterio'])){
   //Construyes un array con todas las palabras:
   $array_keywords = explode("+", $_GET["criterio"]);
 
   //Construyes el sql:
   $sql = "SELECT * FROM producto.allista WHERE";
   //Agregas el contenido de la cláusula WHERE, recorriendo el array
   foreach($array_keywords as $posicion=>$keyword){
      //Si es la primera, no se agrega el "OR".
      $sql .= ($posicion!=0)?' OR':'';
      //Se agrega una condición.
      $sql .= " busqueda LIKE '%".$keyword."%'";
   }
   //el resto lo haces igual
   $res=mysql_query($sql);
   //etc, etc, etc
 
} 
    
  Saludos
