Much has been written on the various techniques for using pagination in Movable Type. Jesse Gardner posted an entry on PlasticMind that gives a good explanation of some of the more popular approaches, their benefits and drawbacks.
I tested Chad Everett's Smarty approach on a blog where the category archives were getting out of hand. (And it's still using the 3.5 templates though powered by 4.21, so monthly categories are not used). Chad's example works, but I had to change the publishing for categories to dynamic and wanted to show page numbers and style them to fit with the blog's theme.
Previous | Next
Mark Carey's Pagination Plugin will only work with the index page. You need Pagination Pro to paginate your Category, Author, date-based archives, and Entry archives.
Creative Spirits offers a javascript approach to pagination. It requires 3 plugins to work and will create hidden "pages" that are viewable on request. An interesting tutorial but not for the faint-hearted.
After much searching, I found a plugin called Paged Archives that requires very little template editing and can be used on the main index, category and date-based archives that use static publishing. This plugin is free, and can be styled however you wish.
Styled "out of the box"
Or, you might give XComment a go. It's a free plugin that uses jQuery for pagination.