I've added paging to a Repeater a couple of time, though rather infrequently. Every time I take up the task again I either have to dig through old code or search Google once again. This time around I went straight to Google and found a nice simple implementation in an article on 4GuysFromRolla by Harrison Enholm, Adding Paging Support to the Repeater or DataList with the PagedDataSource Class. I have used this approach before, but wanted to list it here for future reference so I could find it easier.
Rather than go into details I'll defer to the article as he covers everything well enough. I will say that I did divert from the article's implementation in one small detail. The author chose to store his CurrentPage property (for maintaing his current page index across postbacks) in the ViewState. I try to keep ViewState turned off whenever I can so I chose to use a HiddenField instead.