if you have enabled Gmail's latest Google+ inspired user interface design refresh which is part of Google's multi-month UI design refresh process across Google Products -- you may ghave notice that the new interface has replaced "pagination links with arrow buttons".
However, the navigation links that sent you to the back and forth are still available in the new interface.
Just click the message similar to "11-20 of 3903" from the screenshot below and you'll see the two options that appeared to be missing.
This works for Gmail's search results and when you click one of the labels. For example, you can go to the "All Mail" system label, click the pagination message, select "Oldest" and find the first messages from your Gmail account.
For the search terms that return a lot of results, the only pagination feature that works is "newest" because Gmail shows vague estimations for the number of results like "1-20 of hundreds" or "1-20 of thousands" and it can't determine the last page of results.
[Thanks, Jpp, Alex]