Este es un codigo que obtuve desde uno de los tantos blogs que recorro dia a dia y que realmente me gusto mucho! Aunque le encontre un par de detalles que a mi gusto rompian la estetica por lo cual me di el gusto de modificarlo. A continuación esta el codigo de cada archivo y al final el archivo listo para bajar:

index.php

Incluir el siguiente codigo en la cabecera del index.php:

<link rel="stylesheet" href="index.css" type="text/css" />
<script type="text/javascript" src="ajax.js"></script>

Luego en el cuerpo del index agregar el siguiente contenedor:

<div style="margin:auto;width:100%;text-align:center;">
<div id="contenido">
<?php include('paginador.php')?>
</div>
</div>

A continuación va la hoja de estilos:
index.css

table {
	font-family: Verdana, Arial, Helvetica, sans-serif;
	border-collapse: collapse;
	border-left: 1px solid #ccc;
	border-top: 1px solid #ccc;
	color: #333;
}
 
table caption {
	font-size: 1.1em;
	font-weight: bold;
	letter-spacing: -1px;
	margin-bottom: 10px;
	padding: 5px;
	background: #efefef;
	border: 1px solid #ccc;
	color: #666;
}
 
table a {
	text-decoration: none;
	border-bottom: 1px dotted #f60;
	color: #f60;
	font-weight: bold;
}
 
table a:hover {
	text-decoration: none;
	color: #fff;
	background: #f60;
}
 
table tr th a {
	color: #369;
	border-bottom: 1px dotted #369;
}
 
table tr th a:hover {
	color: #fff;
	background: #369;
}
 
table thead tr th {
	text-transform: uppercase;
	background: #e2e2e2;
}
 
table tfoot tr th, table tfoot tr td {
	text-transform: uppercase;
	color: #000;
	font-weight: bold;
}
 
table tfoot tr th {
	width: 20%;
}
 
table tfoot tr td {
	width: 80%;
}
 
table td, table th {
	border-right: 1px solid #ccc;
	border-bottom: 1px solid #ccc;
	padding: 5px;
	line-height: 1.8em;
	font-size: 0.8em;
	vertical-align: top;
	width: 20%;
}
 
table tr.odd th, table tr.odd td {
	background: #efefef;
}

Y el paginador.php que es el archivo que deberian modificar con la consulta a la tabla deseada:

<?php
require('conexion.php');
$RegistrosAMostrar=4;
 
global $PagAct;
 
//estos valores los recibo por GET
if(isset($_GET['pag'])){
	$RegistrosAEmpezar=($_GET['pag']-1)*$RegistrosAMostrar;
	$PagAct=$_GET['pag'];
//caso contrario los iniciamos
}else{
	$RegistrosAEmpezar=0;
	$PagAct=1;
 
}
$Resultado=mysql_query("SELECT * FROM empleado ORDER BY nombres LIMIT $RegistrosAEmpezar, $RegistrosAMostrar",$con);
echo "<table width=\"100%\">";
echo "<thead>";
echo "<tr>";
echo "<th>Nombres</th>";
echo "<th>Departamento</th>";
echo "<th>Sueldo</th>";
echo "</tr>";
echo "</thead>";
echo "<tbody>";
while($MostrarFila=mysql_fetch_array($Resultado)){
	echo "<tr>";
	echo "<td>".$MostrarFila['nombres']."</td>";
	echo "<td>".$MostrarFila['departamento']."</td>";
	echo "<td>".$MostrarFila['sueldo']."</td>";
	echo "</tr>";
}
echo "</tbody></table>";
 
//******--------determinar las páginas---------******//
$NroRegistros=mysql_num_rows(mysql_query("SELECT * FROM empleado",$con));
 
$PagAnt=$PagAct-1;
$PagSig=$PagAct+1;
$PagUlt=$NroRegistros/$RegistrosAMostrar;
 
//verificamos residuo para ver si llevará decimales
$Res=$NroRegistros%$RegistrosAMostrar;
// si hay residuo usamos funcion floor para que me
// devuelva la parte entera, SIN REDONDEAR, y le sumamos
// una unidad para obtener la ultima pagina
if($Res>0) $PagUlt=floor($PagUlt)+1;
 
//desplazamiento
echo "<div>";
echo "<a onclick=\"Pagina('1')\">Primero</a> ";
if($PagAct>1) echo "<a onclick=\"Pagina('$PagAnt')\">Anterior</a> ";
echo "<strong>Pagina ".$PagAct."/".$PagUlt."</strong>";
if($PagAct<$PagUlt)  echo " <a onclick=\"Pagina('$PagSig')\">Siguiente</a> ";
echo "<a onclick=\"Pagina('$PagUlt')\">Ultimo</a>";
echo "</div>";
?>

Y por ultimo el ejemplo terminado listo para descargar!