Nell'attesa di una risposta, mi sono risposto da solo

Bastava passare le due variabili attraverso lo script di paginazione e porre una condizione if nella pagina gallery. Riporto la soluzione per chiunque ne avesse bisogno:

Questo è lo script paginazione_dati.php

$paginazione = "PAGINE:
[";
for($i = 1; $i <= $tot_pages; $i++) {
if($i == $current_page) {
$paginazione .= $i . " ";
} else {
$paginazione .= "<a href=\"?page=$i&categoria=".$_POST['ricerca']."&marca=".$_POST['ricerca_marca']."\" title=\"Vai alla pagina $i\">$i</a> ";
}
}
$paginazione .= "]";


E questa la condizione all'inizio di gallery.php:

if((!isset($_POST['ricerca'])) && (!isset($_POST['ricerca_marca']))) {
$_POST['ricerca']= $_GET['categoria'];
$_POST['ricerca_marca']= $_GET['marca'];
}