Hi - I need some rewrite help please.

http://mysite.com/?page=2 to http://mysite.com/page/2/

and

http://mysite.com/?s=searchterm&page=2 to http://mysite.com/page/2/?s=searchterm

Thanks.