Código:
include "conexion.php";
$sql = "select id, nombre, apellido, direccion, estado from cliente";
$cliente = mysql_query($sql, $con);
echo "<table>";
while ($rs_cliente = mysql_fetch_assoc)
{
echo "<tr>";
echo "<td>$rs_cliente['id']</td>";
echo "<td>$rs_cliente['nombre']</td>";
echo "<td>$rs_cliente['apellido']</td>";
echo "<td>$rs_cliente['direccion']</td>";
echo "<td>$rs_cliente['estado']</td>";
echo "</tr>";
}
echo "</table>";
en lo de paginación, existen ejemplos ya hechos donde puedes adaptar tu codigo.
http://www.elguruprogramador.com.ar/articulos/paginacion-en-php.htm
espero les sea de ayuda