yearly pagination for custom post type

I have a custom post type type set-up that pulls in newsletter information. I’d like to display yearly pagination for this post-type. So far I have managed to display pagination with ‘paged’ and ‘posts_per_page’ for my custom post type, but can not figure out how to specify this pagination by year.

I’ve been asked to have it look something like this:

2012 Previous Year link | Next Year link

with the posts for each year below.

Does anyone have any suggestions? Thank You!