Hola,
Simplemente antes de comenzar todo lo de la paginacion y las consultas y mostrar los resultados, haz un:
Código PHP:
if (empty($_GET["criterio"])) {
echo "Debe especificar un termino de busqueda";
} else {
// el codigo de paginacion y busqueda
}
Saludos.
PD: Leyendo ese tutorial, me doy cuenta como distintos programadores pueden llegar a crear codigos muy parecidos. Porque si se realiza una busqueda en este foro por "paginar" y "paginacion", se veran codigos muy parecidos, incluso el nombre de las variables.