How can I paginate a list of related posts?

My client’s home page displays a paginated list of posts with thumbnails. Each list item, when clicked, navigates to a single post or page, and then uses a separate query to generate the same list of posts at the page footer.

Pagination works just fine on the home page, however, he wants the list underneath single posts to be paginated the same as the home page.

That is, we would be at website.com/post-12345 and it would show a list of posts 1-12 underneath. There would be “newer posts” and “older posts” buttons which should swap the list of posts 1-12 for a list of posts 13-24, for example, while displaying the same post, ie remaining at website.com/post-12345.

I thought of simply calling all the posts via get_posts() and switching between them using JavaScript, but there will eventually be hundreds of posts and thumbnails and the page would take forever to load.

Is there a way to achieve this type of pagination that isn’t so clumsy?

I’m open to solutions in PHP, JavaScript, even Ajax.