I have noticed that users and search engine spiders are still going on the original un-mod_rewrite'd versions of my pages. Now to combat this my question is, is it possible to 301 redirect the original page to the new page with mod_rewrite without it screwing up the rewrite?

depends on how the rewrite is done

Do we get some example code? because there are so many ways to code the same thing in .htaccess any answers could send you down the wrong track.

It's just your standard RewriteRule gallery.php?id=(.*) gallery-$1.html

Problem is the search engine still indexs both. I want to do a permanent redirect if possible

RewriteRule gallery.php?id=(.*) gallery-$1.html [R=301]

It seems that did not work. It redirected the rewritten pages to the original .php?id= pages.