Erro ao tentar executar paginação.

Olá pessoal!

Estou tentando utilizar o seguinte código.

<?php

// bloco 1 - conecte-se ao banco de dados
$banco = 'escola_aluno'; // Define o nome do banco de dados
include("conexao.php"); //Realiza a conexão
mysql_select_db($banco); //Selecion o banco de dados

// Maximo de registros por pagina
$maximo = 2;

// Declaração da pagina inicial

$pagina = $_GET["pagina"];
if($pagina == "") {
 $pagina = "1";
}

// Calculando o registro inicial

$inicio = $pagina - 1;
$inicio = $maximo * $inicio;

// Conta os resultados no total da query

$strCount = "SELECT COUNT(*) AS 'num_registros' FROM Aux_Estado";
$query = mysql_query($strCount);
$row = mysql_fetch_array($query);
$total = $row["num_registros"];

###################################################################################
// INICIO DO CONTEÚDO

// Realizamos a query
$sql = mysql_query("SELECT * FROM Aux_Estado LIMIT $inicio,$maximo");

// Exibimos os nomes dos produtos e seus repectivos valores
while ($linha = mysql_fetch_object($sql)) {

//echo "<b>" . $linha->Nome . "</b> (R$ ". $linha->valor.")<br />";
echo "<b>" . $linha->Nome . "</b>";
}

// FIM DO CONTEUDO
###################################################################################

$menos = $pagina - 1;
$mais = $pagina + 1;

$pgs = ceil($total / $maximo);

if($pgs > 1 ) {

echo "<br />";

 // Mostragem de pagina
 if($menos > 0) {
	echo "<a href=".$_SERVER['PHP_SELF']."?pagina=$menos>anterior</a> ";
 }

 // Listando as paginas
for($i=1;$i <= $pgs;$i++) {
	if($i != $pagina) {
 echo " <a href=".$_SERVER['PHP_SELF']."?pagina=".($i).">$i</a> | ";
	} else {
 echo " <strong>".$i."</strong> | ";
	}
}

if($mais <= $pgs) {
	echo " <a href=".$_SERVER['PHP_SELF']."?pagina=$mais>próxima</a>";
}
}
?>

Mas ao acessar a página pela primeira vez ocorre o seguinte erro:

Notice: Undefined index: pagina

Logo depois quando acesso os links ocorre tudo como o esperado.

Se alguém puder me ajudar ficarei muito grato pois sou iniciante e há dois dias estou encucado na tentativa de resolver essa situação.

Walhew!