You could probably get away with using scenario outlines to keep the repetition down in your feature file, but be aware that it will expand to a very large number of actually-run scenarios, so it'll be slower than you'd expect. Something like this should probably work, assuming 5 books per page. I'll leave the step definitions as an exercise, but they should be pretty straightforward.
I should also mention that I haven't actually run this, so take any syntax errors with a grain of salt.
Feature: Book Browsing Pagination
Scenario: No results
Given I have 0 books
When I view all books
Then I should see "No results" on the page
Scenario: Some results
Given I have 3 books
When I view all books
Then I should see "Book 1"
And I should see "Book 2"
And I should see "Book 3"
Scenario: Page links
Given I have <count> books
When I view all books from page <page>
Then I should see a link to page <target page>
Examples:
| count | page | target page |
| 8 | 1 | 2 |
| 8 | 2 | 1 |
| 13 | 1 | 2 |
| 13 | 1 | 3 |
| 13 | 2 | 1 |
| 13 | 2 | 3 |
| 13 | 3 | 1 |
| 13 | 3 | 2 |
Scenario: Page links for current page
Given I have <count> books
When I view all books from page <page>
Then I should see a disabled pagination link to page <page>
Examples:
| count | page |
| 8 | 1 |
| 8 | 2 |
| 13 | 1 |
| 13 | 2 |
| 13 | 3 |
Scenario: Next Page links
Given I have <count> books
When I view all books from page <page>
Then I should see a link "Next Page"
When I click "Next Page"
Then I should be on page <next page> # assert against query params maybe?
# alternately, to keep page requests down, one could use something like:
# Then I should see a link "Next Page" going to "?p=<next page>"
Examples:
| count | page | next page |
| 8 | 1 | 2 |
| 13 | 1 | 2 |
| 13 | 2 | 3 |
Scenario: Next Page links on last page
Given I have <count> books
When I view all books from page <page>
Then I should see a disabled pagination link "Next Page"
Examples:
| count | page |
| 8 | 2 |
| 13 | 3 |
Similar scenarios could be used for checking the link state of Previous/First/Last as for Next, and you could add some followup clicking to the Page Links scenario similar to what the Next Page scenario is doing if you wanted. You might also want to add extra examples to check that your pagination is at exactly 5, since the examples I've picked would also pass if pagination was 6 per page. Depends on what exactly your goals are for checking the pagination functionality.
If you eventually decide on something other than will_paginate, then the only things you'd need to look at changing might be a few of the steps (like the disabled pagination ones).
And as you mention asking for links, this might make a good blog post too ;)