Eu já fiz uma em Velocity.
É bem chatinho mesmo viu cara. O projeto Jakarta tem componentes para fazer isso, não me lembro exatamente qual, ele usa taglibs :8
Mas se vc quiser fazer na mão tbm dá.
Vc vai ter q ter parametros para definir o total de registros, registros por pagina, pagina anterior e pagina posterior.
Digamos que vc tenha 100 registros e só queira mostrar 15 por página.
int totRegs = 100;
int regsPerPag = 15;
int totPages = totRegs/regsPerPag; //Aqui vc tem o total de paginas;
Ai vc vai ter que fazer rotinas pra gerar a página seguinte e anterior
Por exemplo, a próxima página iria começar no registro numero 16, entao vc passa 16 como parametro e faz a consulta pegando do 16º registro até os 15 seguintes, e assim vai para as outras.
Sei q ficou meio vago, mas se vc seguir esse principio dá pra fazer uma rotininha legal, a minha ficou meio grande, mas funcionou bacana :P