A supplement to a conversation that has come up a couple of times: Pagination Gallery: Examples and Good Practices

The author lists seven keys to good pagination:

1. Provide large clickable areas
2. Don’t use underlines
3. Identify the current page
4. Space out page links
5. Provide Previous and Next links
6. Use First and Last links (where applicable)
7. Put First and Last links on the outside

There are tons of screenshots of both good and bad pagination, which makes this a great reference.