To implement simple paging in Azure Storage in relatively straight forward: Paging with Windows Azure Table Storage. This can be implemented with continuation token functionality.
But.
This is just a start for the serious paging. First problem is sorting. You can not do OrderBy in Azure Table. What would be the best solution to overcome this? Pages must be sorted, that's the fact.
Second problem, when come to the paging is to know number of total pages, with just continuation token functionality this is not possible. To do at every page ".Count()" seems to me very inefficient (since partitions could be on multiple servers, for instance).
Third problem is, related to the second, even you can count how many pages you have, how to "connect" counted pages to the actuals continuation tokens? This is the biggest mystery for me. How to get a continuation from the specific table row?
I would be very happy, if correct solution could be provided. I must admit I also have one and I will write it in one of the answers below.