Using posts.nextPageUrl I can output this: http://example.com/?page=2. Now, how do I get the next post title (and the previous one if it is not the first/most recent post)?

For this you have to extened plugin. I have wrote a prevnextComponent for this task. There I also fetch title.

When will you publish your plugin?

You need to write your own logic preferably in a model method like function getPreviousPost() and function getNextPost() that do what you want. Note that there is no one-solution-fits-all that's why you need to implement it yourself.

It is a matter of choice whether you want to do it as a component as @Crazymodder said or want to provide this functionality through the post model itself such that it could be used like e.g., so in twig <a href="{{ post.previous.url() }}">Previous Post</a> (of course adjusted to your post model structure).

@Atok,

I have write this some time ago only for testing purpose. For me its not a full functional plugin which I want to publish. I don't know if it exactly fits your requirements. Also see what philipptempel has written. If you have no idea what to do pls. write here. I will search for that snippet and post it here.

You can use this plugin http://octobercms.com/plugin/pollozen-nextprevpost