Using mod_rewrite to 301 redirect get vars to new clean URLs

Add this somewhere in your htaccess:

RewriteCond %{THE_REQUEST} ^([A-Z]{3,9})\ /index\.php\?p=([^&]+)&o=(.+)\ HTTP
RewriteRule index.php /%2/%3 [R=301,L]

And if you want to cover the case where there's no "temporary_override", add this too:

RewriteCond %{THE_REQUEST} ^([A-Z]{3,9})\ /index\.php\?p=(.+)\ HTTP
RewriteRule index.php /%2 [R=301,L]

Closer, but I can't figure out how to get rid of the GET vars which are being added to the URL or why it's redirecting to the root directory instead of to the RewriteBase directory

Add a ? at the end of /%4/%5 to get rid of the query string. And remove the leading / from /%4/%5 to keep it from rewriting to the root. So, for example, one of your rules should look like this:

RewriteCond %{THE_REQUEST} ^([A-Z]{3,9})\ \/([^\/]+\/)*(index\.php)?\?[op]=([^&]+)&[op]=(.+)\ HTTP\/
RewriteRule ^index\.php$ %4/%5? [R=301,L]

You're going to want to use the following:

RewriteRule ^([^/]+)/?$ index.php?p=$1 [L,QSA]
RewriteRule ^([^/]+)/([^/]+)/?$ index.php?p=$1&o=$2 [L,QSA]

This way, example.com/page_name gets internally passed to index.php?p=page_name and example.com/page_name/operation gets passed to index.php?p=page_name&o=operation. Jon Lin's answer seems to have been doing the opposite, which I hadn't noticed last night.

There shouldn't be any need for any RewriteConds except to avoid conflict with other rules that you might have, just to clarify.

Change 2 of your RewriteRule lines should end with ? like this:

#if 2 GET Vars
RewriteCond %{THE_REQUEST} ^([A-Z]{3,9})\ /([^/]+/)*(index\.php)?\?[op]=([^&]+)&[op]=(.+)\ HTTP\/
RewriteRule ^ /%4/%5? [R=301,L]

#if 1 GET Var
RewriteCond %{THE_REQUEST} ^([A-Z]{3,9})\ /([^/]+/)*(index\.php)?\?[op]=(.+)\ HTTP\/
RewriteRule ^ /%4? [R=301,L]