I spent hours researching the problem, and just want to share a solution in case you ever need to implement paging for asp:DataList in .NET 2.0.
My specific requirement was to have "Previous" and "Next" links and page number links.
I moved this from the question, so it doesn't appear as "Not Answered"...
PagedDataSource solution in this article was the most elegant and simple solution for this problem.
If you have a better solution - post it here please.
p.s. I'm not affiliated with that website in any way.