1. Plugin solution (though not quite what you ask for):
http://lesterchan.net/wordpress/readme/wp-pagenavi.html
2. Hand-coded solution:
We can collect the current page # this way:
<?php
$pagenum = (get_query_var('paged'));
?>
However, this will be empty in certain cases, such as on the home page. But we can use an old trick of mine to set a proper page number no matter what:
<?php
$pagenum = (get_query_var('paged')) ? get_query_var('paged') : 1;
?>
Still not useful yet. So let's add a bit to it:
<?php
$pagenum = (get_query_var('paged')) ? get_query_var('paged') : 1;
$nextnum = $pagenum + 1;
$prevnum = $pagenum - 1;
?>
See where we're going with this? Finally, let's make this into something you can implement by merging it with the posts_nav_link() template tag:
<?php
$pagenum = (get_query_var('paged')) ? get_query_var('paged') : 1;
$prevnum = $pagenum - 1;
$nextnum = $pagenum + 1;
posts_nav_link(' | ', '« Page ' . $prevnum, 'Page ' . $nextnum . ' »');
?>