Pagination can take many different forms. However, it's generally made up of labels, indicators, arrows, or some combination of the three. There's no single perfect implementation. But we can get close by considering each of these elements, in context, before they are removed—or implied.
First, you should look at the type of content being paginated, and—more importantly—how it's sorted. This should define the language used for labels. In most cases, contacts are sorted alphabetically, blog posts are sorted reverse-chronologically, and search results are sorted by relevance.
When paginating their results, Google use the labels Next to load more results and Previous to go back from pages other than the first. They also use a page indicator to show which page you are on (more on that in a minute).
Google use Previous and Next. They also indicate which page you are on.
This is clear. You start on the first page and move left-to-right to the next page. You always know where you are, and what clicking Next or Previous will do. This labeling makes sense for paginating content sorted by relevance (or alphabet). It does not, however, for paginating chronologically sorted content.
Blogs are almost always sorted in reverse-chronological order. This means the newest content is on the front page, with subsequent pages containing older content. If the label Next was used on the front page, the user could only assume this would take them to the next page of content; it's the only option. The user may comprehend the label, but it isn't the clearest option. Older or even Older Posts is more explicit.
The pagination system should also be consistent throughout a site. On a post page, if the label Next was used, the user would have very little idea whether they would be taken to the next-newest or the next-oldest post. With chronologically ordered content, Newer and Older aid the users comprehension more than Previous and Next.
Google give the user every element possible to aid comprehension. But they are not all necessary. Pagination is such a strong design pattern that, when you remove detail, the user's brain fills it in. If Google's pagination is cut in half (as below) both the top and bottom halves work on their own.
The top of Google’s pagination.
Removing the bottom means there are no labels and no numerical indicator. However, the left and right chevrons imply Previous and Next, and the oooooooooo replaces a traditional numerical indicator. This still gives the user a fairly clear idea of where they are and what clicking each arrow will do.
The bottom of Google’s pagination.
Removing the top makes this far less graphical, yet equally—or more—clear. There are no arrows but direction is implied; Next is to the right of the page, and Previous is to the left. Bing do exactly this:
Designers can make good use of these implied elements by considering, and then removing them. But if they aren't considered, they can confuse the user.
I would argue that in the case of reverse-chronologically ordered content—whether arrows are used or not—Newer should always be to the left of the page and Older to the right. In turn, when content is sorted by relevance or alphabet, Previous should always be to the left of the page and Next to the right.
The pagination on my blog (usually obscured by infinite scrolling).
The reason for this is the page indicator; it may be implied, but it's always there. English reads left-to-right, therefore, a list of numbers should be written left-to-right.
Bing’s pagination reversed.
In the above example I've reversed Bing's pagination. If the page indicator was removed, this might appear to make sense. But with it present, it clearly doesn't. If the indicator (or labeling, arrows etc.) is going to be implied, the other elements should still follow the left-to-right pattern.
When elements of pagination are removed, they are still implied. Consider these implied elements next time you're designing pagination.