Fiz muitas buscas pela internet para encontrar um script legal para paginar os dados do banco de dados de meus sites e nenhum estava a altura do que eu precisava.
Então encontrei este vídeo: http://www.youtube.com/watch?v=GUJCHiodteA que ensina a mostrar como criar uma paginação de elementos dentro de um array, no caso específico do vídeo, imagens.
Aí fiz algumas adaptações, e consegui o seguinte código para paginar. Vai estar todo comentado, sei que não é perfeito, mas funcionou bem para mim.
Esclareço que sou iniciante em PHP e MySQL e ainda falta muiiiito para aprender.