Cita: Primero cargaría en una tabla del DataSet toda la consulta de la base de datos, que nunca van a ser más de 50 registros. Dinamicamente creo otra tabla, que va a ser la que va a contener los registros que se están mostrando en pantalla, es decir, esta será la tabla que realmente va a ser la fuente de datos del control DataList.
Mira... te podríamos hechar la mano pero me llevaría un rato ir explicando paso a paso lo que se podría mejor.
Para empezar podrías mejor paginar con un daterader que con un dataset ya que en cuestiones de perfomance es mas pesado un dataset, claro que el código para paginar con un reader es un poco mas laborioso pero es mas ligero.
Lo que puedes hacer es colocar fragmentos de código de mas o menos lo que pretendes hacer e irlo armando aqui mismo con las sugerencias de los demas.
Salu2 y cualquier cosa andamos por aqui..