A Very Useful Plugin is MTPaginate 1.24 by Stepan Riha.
One of the things that was bothering me was the ever increasing length of my Category and Monthly Archive pages. Having it load all in one page is annoying and inefficient to say the least. By following the very detailed instructions above, I was able to implement it with very little problems.