Puoi fare con i parametri GET e POST concatenati..
Es.:

 $tipo=''; if (isset($_POST['tipo'])){$tipo=$_POST['tipo'];}    
$regione=''; if (isset($_POST['l1'])){$regione=$_POST['l1'];}
if($_GET['page'] != 1){
$reg_get = $_GET['reg_get'];
$tipo_get = $_GET['tipo_get'];}

Poi, quando ti crei il link con le pagine :
<a href = "mio.php?reg_get=$reg_get ecc...

Ola

[...]

Grazie per aver risposto. Ho due domande che son un po' in confusione,

$reg_get = $_GET['reg_get'];
$tipo_get = $_GET['tipo_get'];}

che valori devo passare dentro $_GET['']? Nel mio caso gli passo ''tipo'' e ''l1'' giusto?

Nel link finale ho : <a href="?page=$i" title="Vai alla pagina $i">$i</a> com lo modifico esattamente?

@La prima domanda : SI
La seconda :
<a href = "?page=".$i."&reg_get=$reg_get&tipo_get=$tipo_get">

[...]
Ok allora, il mio codice è questo:

$tipo=''; if (isset($_POST['tipo'])){$tipo=$_POST['tipo'];}
$regione=''; if (isset($_POST['l1'])){$regione=$_POST['l1'];}
if($_GET['page'] != 1){
$reg_get = $_GET['l1'];
$tipo_get = $_GET['tipo'];}
..
..
$paginazione .= "<a href="?page=$i&l1=$reg_get&tipo=$tipo_get">$i</a> ";

però non mipassa i valori comunque, il link dell apagina è questo quando clicco sulla successiva:

miosito.it/paginazione.php?page=2&l1=&tipo=

cosa può essere?

Prova con...
[PHP]if(!empty($_GET['reg_get'])){
$paginazione .= "<a href="?page=$i&l1=$reg_get&tipo=$tipo_get ">$i</a> ";}else{
$paginazione .= "<a href="?page=$i&l1=".$_POST['l1']."&tipo=".$_POST['data']."">$i</a> ";
}[/PHP]

Ciao, scusa ma mi sto incasinando, ti copio il codice completo come è ora con i vari commenti:

[PHP]
$tipo=''; if (isset($_POST['tipo'])){$tipo=$_POST['tipo'];}
$regione=''; if (isset($_POST['l1'])){$regione=$_POST['l1'];}

$where=' 1=1 ';
if($tipo!=''){$where.=' AND vino_tipo="'.$tipo.'"';}
if($regione!=''){$where.=' AND idregione="'.$regione.'"';}

// esecuzione prima query
$count = mysql_query('SELECT COUNT(vino_id) FROM vino INNER JOIN regioni ON vino.vino_idregione=regioni.idregione WHERE '.$where);
$res_count = mysql_fetch_row($count);
// numero totale di records
$tot_records = $res_count[0];
// risultati per pagina(secondo parametro di LIMIT)
$per_page = 10;
// numero totale di pagine
$tot_pages = ceil($tot_records / $per_page);
// pagina corrente
$current_page =(!isset($_GET['page'])) ? $pag = 1 : $pag = $_GET['page'];
if($_GET['page'] != 1){
$tipo = $_POST['tipo'];
$regione = $_POST['l1'];}
// primo parametro di LIMIT
$primo = ($current_page - 1) * $per_page;

$query_limit = mysql_query('SELECT *,nomeregione FROM vino INNER JOIN regioni ON vino.vino_idregione=regioni.idregione WHERE '.$where.' ORDER BY vino_nome LIMIT '.$primo.','.$per_page);

while($results = mysql_fetch_array($query_limit)){
$output.=" <tr>\n <td>";
$output.="<a href="scheda_vino.php?id=" . $results['vino_id'] . "">" . $results['vino_nome'] . "</a>
";
$output.="</td>\n </tr>\n";
}

// in questa cella inseriamo la paginazione
$paginazione = "Pagine totali: " . $tot_pages . "
[";
for($i = 1; $i <= $tot_pages; $i++) {
if($i == $current_page) {
$paginazione .= $i . " ";
} else {
if(!empty($_GET['reg_get'])){
$paginazione .= "<a href="?page=$i&regione=$regione&tipo=$tipo ">$i</a> ";}else{
$paginazione .= "<a href="?page=$i&regione=".$_POST['l1']."&tipo=".$_POST['tipo']."">$i</a> ";
}
}
}
$paginazione .= "]";

$output.=" <tr>\n <td height="50" valign="bottom" align="center">$paginazione</td>\n";

[/PHP]

Dove sbaglio? Non mi passa i parametri.Grazie ancora.

[PHP]if(isset($_GET['reg_get'])){
$tipo = $_GET['tipo_get'];
$regione = $_GET['reg_get'];
}else{
$tipo=''; if (isset($_POST['tipo'])){$tipo=$_POST['tipo'];}
$regione=''; if (isset($_POST['l1'])){$regione=$_POST['l1'];}
}
$where=' 1=1 ';
if($tipo!=''){$where.=' AND vino_tipo="'.$tipo.'"';}
if($regione!=''){$where.=' AND idregione="'.$regione.'"';}

// esecuzione prima query
$count = mysql_query('SELECT COUNT(vino_id) FROM vino INNER JOIN regioni ON vino.vino_idregione=regioni.idregione WHERE '.$where);
$res_count = mysql_fetch_row($count);
// numero totale di records
$tot_records = $res_count[0];
// risultati per pagina(secondo parametro di LIMIT)
$per_page = 10;
// numero totale di pagine
$tot_pages = ceil($tot_records / $per_page);
// pagina corrente
$current_page =(!isset($_GET['page'])) ? $pag = 1 : $pag = $_GET['page'];
if($_GET['page'] != 1){
$tipo = $_POST['tipo'];
$regione = $_POST['l1'];}
// primo parametro di LIMIT
$primo = ($current_page - 1) * $per_page;

$query_limit = mysql_query('SELECT *,nomeregione FROM vino INNER JOIN regioni ON vino.vino_idregione=regioni.idregione WHERE '.$where.' ORDER BY vino_nome LIMIT '.$primo.','.$per_page);

while($results = mysql_fetch_array($query_limit)){
$output.=" <tr>\n <td>";
$output.="<a href="scheda_vino.php?id=" . $results['vino_id'] . "">" . $results['vino_nome'] . "</a>
";
$output.="</td>\n </tr>\n";
}

// in questa cella inseriamo la paginazione
$paginazione = "Pagine totali: " . $tot_pages . "
[";
for($i = 1; $i <= $tot_pages; $i++) {
if($i == $current_page) {
$paginazione .= $i . " ";
} else {
if(!empty($_GET['reg_get'])){
$paginazione .= "<a href="?page=$i&regione=$regione&tipo=$tipo ">$i</a> ";}else{
$paginazione .= "<a href="?page=$i&regione=".$regione."&tipo=".$tipo."">$i</a> ";
}
}
}
$paginazione .= "]";

$output.=" <tr>\n <td height="50" valign="bottom" align="center">$paginazione</td>\n"; [/PHP]

Va a metà, ho cambiato i GET in REQUEST perchè non gli passava il valore...adesso se faccio la ricerca per tipo va tutto ok, se la faccio per regione, al primo cambio di pagina mi tiene il valore della regione, al secondo passaggio non mi passa più l'id della regione...come mai fa così?

Cambia questo

[PHP]if(!empty($_GET['reg_get'])){
$paginazione .= "<a href="?page=$i&regione=$regione&tipo=$tipo ">$i</a> ";}else{
$paginazione .= "<a href="?page=$i&regione=".$regione."&tipo=".$tipo."">$i</a> ";
} [/PHP]
Con questo :

[PHP]$paginazione .= "<a href="?page=$i&regione=".$regione."&tipo=".$tipo."">$i</a> ";[/PHP]

Ho risolto, ho fatto io un errore stupido, la combo box regione del form da cui arrivavano i dati l'avevo chiamata l1, recuperavo 'l1' ma poi nella stringa gli passavo 'regione' e andava in palla funzoinava al primo colpo e al secondo passaggio si incasinava il codice. Comunque adesso funziona grazie, ho semplicemente messo:
[php]
$tipo=''; if (isset($_REQUEST['tipo'])){$tipo=$_REQUEST['tipo'];}
$regione=''; if (isset($_REQUEST['regione'])){$regione=$_REQUEST['regione'];}
//resto del codice....

$paginazione .= "<a href="?page=$i&regione=$regione&tipo=$tipo" >$i</a> ";
[/php]

Grazie per il prezioso aiuto! ciao Simone

Prego, di niente!:)
Sempre a disposizione!:D