Para páginar en PHP existen muchas posibilidades. En este caso pongo tres ejemplos muy similares.

Esta es la versión más simple de todas, te mostrará todas las páginas y las enlazará.

/* Variables */
$pagina=1;
$pagina=$_GET['pagina'];
$total_paginas=50;
$parametros_url;

if ($total_paginas > 1) {
        if ($pagina != 1) {
            echo '<li><a href="/?pagina='.($pagina-1).$parametros_url.'"><span aria-hidden="true">&laquo;</span></a></li>';//pagina anterior
        }
 
        for ($i=1;$i<=$total_paginas;$i++) {
            if ($pagina == $i) {
                echo '<li class="current"><a href="#">'.$pagina.'</a></li>';//Página seleccionada
            } else {
                echo '<li><a href="/buscar/?pagina='.$i.$parametros_url.'">'.$i.'</a></li>';//Listado paginas
            }
        }
 
        if ($pagina != $total_paginas) {
            echo '<li><a href="/buscar/?pagina='.($pagina+1).$parametros_url.'"><span aria-hidden="true">&raquo;</span></a></li>';//pagina siguente
        }
    }

¿Qué pasa si tenemos muchas páginas?

Principalmente el mayor problema es que si es un número enorme de páginas las que tiene que mostrar seguramente no quede bien visualmente, para eso podemos controlar su comportamiento.

En este ejemplo se muestran las 10 primeras páginas de la páginación y las seguirá mostrando de 10 en 10. Es ejemplo perfecto por si quieres determinar un buen número de resultados pero teniendo un ancho fijo.

/* Iniciamos las variables */
$pagina=1; //Le damos valor 1 por defecto.
$pagina=$_GET['pagina']; //Para coger el valor por GET
$total_paginas=50; // El numero total de páginas
$parametros_url; //Por si queremos pasar parametros a la url

function mostrar_paginacion($pagina, $total_paginas, $parametros_url){
	//Calculamos la primera y última página a mostrar	
	$primera = $pagina - ($pagina % 10) + 1;
	if ($primera > $pagina) { $primera = $primera - 10; }
	$ultima = $primera + 9 > $total_paginas ? $total_paginas : $primera + 9; 
    if ($total_paginas > 1) {
        if ($primera != 1) {
            echo '<li><a href="/?pagina='.($primera-1).$parametros_url.'" aria-label="Ir a página anterior"><span>Anterior</span></a></li>';//pagina anterior
        }
 
        for ($i=$primera;$i<=$ultima;$i++) {
            if ($pagina == $i) {
                echo '<li><a class="current" href="#" aria-label="Página actual">'.$pagina.'</a></li>';//Página seleccionada
            } else {
                echo '<li><a href="/?pagina='.$i.$parametros_url.'" aria-label="Ir a página '.$i.'">'.$i.'</a></li>';//Listado paginas
            }
        }
 
        if ($pagina <= $total_paginas) {
            echo '<li><a href="/?pagina='.($i).$parametros_url.'" aria-label="Ir a página siguiente"><span>Siguiente</span></a></li>';//pagina siguente
        }
    }
}

//Llamamos a la funcion
mostrar_paginacion($pagina, $total_paginas, $parametros_url);

En este segundo ejemplo se mostrarian las tres páginas siguientes y las tres anteriores si estuvieran. Ejemplo perfecto para hacer algo más comedido.

/* Iniciamos las variables */
$pagina=1; //Le damos valor 1 por defecto.
$pagina=$_GET['pagina']; //Para coger el valor por GET
$total_paginas=50; // El numero total de páginas
$parametros_url; //Por si queremos pasar parametros a la url

function mostrar_paginacion($pagina, $total_paginas, $parametros_url){
	$rango_paginas = $pagina -3;
	$max_iteraciones = $pagina +3;

	if($pagina != 1){
		echo'  <li><a href="/?pagina='.($pagina-1).$parametros_url.'" aria-label="Ir a página anterior"><span>Anterior</span></a></li>';
	}

	for($rango_paginas; $rango_paginas <= $max_iteraciones;$rango_paginas++){
		if($rango_paginas>0 && $rango_paginas <= $total_paginas ){
			if($pagina == $rango_paginas){
			echo '<li><spa class="current">'.$rango_paginas.'</span></li>';
        }else{
			echo '<li><a href="/?pagina='.$rango_paginas.$parametros_url.'" aria-label="Ir a página '.($rango_paginas).'">'.($rango_paginas).'</a></li>';
			}
		}
	}

	if($pagina != $total_paginas){
		echo '<li><a href="/?pagina='.($pagina+1).$parametros_url.'" aria-label="Ir a página siguiente"><span>Siguiente</span></a></li>';
	}
}

// Llamamos a la funcion
mostrar_paginacion($pagina, $total_paginas, $parametros_url);