Paging and Clean URLs

I apologize if this has been discussed before but I can’t seem to any relevant answers after much searching of these forums and on google.

I’m a wordpress newbie; got everything running well so far on v1.2.2. The only thing I can’t figure out is how to get clean URLs on after turning on pagination. This is for the main page, archives and category pages. I’ve figured out how to edit the .htaccess file to accept clean URLs and return the right results, but I can’t figure out how to get the “Next” and “Previous” links to write the clean URLs in the page itself.

For example, I’d like “Next Page” link to be “http://www.mysite.com/page/2/” instead of “http://www.mysite.com/index.php?paged=2”;

Is this behavior available in v1.2.2? Or can I get this behavior by installing a plugin or hack?

Or do I need to a version of v1.5? And if so, is there a somewhat stable version of v1.5 that I would be able to download somewhere?