During the recent redesign of my blog, I decided that I wanted to have pretty pagination with numbers instead of the WordPress default Older/Newer Posts links. The plugin I decided to use was WP Page Numbers by Jens Törnell.
This is how the pagination for page one of my home looks now:
For page six you can see more of what the plugin can do:
Do I have twenty pages of posts already?