Te pongo la sentencia y al final te explico:
Código PHP:
$nombre = $_POST['nombre'];
$apellido = $_POST['apellido'];
$query = mysql_query("SELECT * FROM tutabla WHERE INSTR(NOMBRE, '$nombre')>0 or INSTR(APELLIDO, '$apellido')>0 order by INSTR(NOMBRE, '$nombre')*INSTR(APELLIDO, '$apellido') DESC");
La funcion INSTR() devuelve el numero de posicion del segundo parametro dentro del primer parametro, de modo que nos va a devolver los registros donde encuentre $nombre en el campo NOMBRE o $apellido en el campo APELLIDO. Pero luego además como la funcion INSTR() nos devuelve un numero de 0 para arriba, hemos incluido un ORDER BY que multiplica los dos valores de modo que van a salir primero aquellos registros donde encuentre ambos campos, porque si los encuentra estara multiplicando dos numeros mayores que cero, pero si en un registro encontramos el nombre pero no el apellido estara multiplicando un valor entero por 0, lo cual es 0. Este order by es bastante mejorable pero no me queria liar jeje