I have tied a couple things to get this to work and no matter what it will not, please someone help me.

I have a site lets call it example.com

on the site I have a href links that look like this
<a href="http://www.example.com/index.php?page=My_Home_Page">HOME</a>
<a href="http://www.example.com/index.php?page=My_About_Page">ABOUT</a>

To display the correct content on the correct page when each link is clicked I am using this

PHP Code:

<?php
$nav = $_GET['page']; //gets the variable inside page query string and stores it into the variable $nav

if (!isset ($_GET['page'])){
$nav = "My_Home_Page"; //if no query string is available then use the data from "My_Home_Page"
}

if ($nav == 'My_Home_Page'){ //if the query string is equal to "My_Home_Page" then display the following
?>
<!-- BREAK OUT OF PHP TO ENTER HTML -->
<H1>HOME</H1>
<!-- RETURN TO PHP -->
<?php
}

else if ($nav == 'My_About_Page'){ //if the query string is equal to "My_About_Page" then display the following
?>
<!-- BREAK OUT OF PHP TO ENTER HTML -->
<H1>ABOUT</H1>
<!-- RETURN TO PHP -->
<?php
}

Now this is all working and has been for a while however now I am trying to do some seo and I would like to rewrite all my urls to be more seo friendly, so I am on an apache server for my hosting so I figure I would use the .htaccess file.

This is my .htaccess file

Options +FollowSymLinks
Options -Indexes

RewriteEngine on

# THIS PART IS WORKING IF I ENTER http://example.com IT ADDS THE www to be http://www.example.com
RewriteCond %{HTTP_HOST} ^example.com
RewriteRule ^(.*)$ http://www.example.com/$1 [R=permanent,L]

# THIS IS NOT WORKING
RewriteRule http://www.example.com/index.php?page=My_Home_Page http://www.example.com/SEO-Home-Page-with-nice-keywords
RewriteRule http://www.example.com/index.php?page=My_About_Page http://www.example.com/SEO-About-Page-with-nice-keywords

# I HAVE NO IDEA IF THIS IS WORKING OR NOT MY ISP TOLD ME TO ENTER THIS BECAUSE I KEPT GETTING OLD CONTENT
# APPARENTLY THIS EXPIRES THE CACHE AFTER ONLY 1 MINUTE
<FilesMatch "\.(html|htm|php)$">
Header set Cache-Control "max-age=60, private, proxy-revalidate"
</FilesMatch>

I now assume that if I am on my site and I click on the about page link, it should take me to the about pages content, however my url should now be http://www.example.com/SEO-About-Pag...-nice-keywords

this is not working though it just shows me the content of the about page and the url remains as it always was with the php query string

The other part is working though, when I type in the url without a www, it adds it in for me.

Please help.

mod_rewrite and query strings aren't that straightfroward - have a look at http://www.simonecarletti.com/blog/2...-query-string/ for some further info.

Your better off writing the links with the new structure, and using PHP to determine the page.

Links:
<a href="http://www.example.com/SEO-Home-Page-with-nice-keywords">HOME</a>
<a href="http://www.example.com/SEO-About-Page-with-nice-keywords">ABOUT</a>

Options +FollowSymLinks
Options -Indexes
RewriteEngine on
RewriteCond %{HTTP_HOST} !^www\.example\.com [NC]
RewriteRule ^(.*)$ http://www.example.com/$1 [R=301,L]
# Don't rewrite real files or directories
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^([A-Za-z0-9-_]+)$ index.php?page=$1 [QSA,L]
# I HAVE NO IDEA IF THIS IS WORKING OR NOT MY ISP TOLD ME TO ENTER THIS BECAUSE I KEPT GETTING OLD CONTENT
# APPARENTLY THIS EXPIRES THE CACHE AFTER ONLY 1 MINUTE
<FilesMatch "\.(html|htm|php)$">
Header set Cache-Control "max-age=60, private, proxy-revalidate"

PHP Code:

<?php
  
  $nav = (isset($_GET['page'])) ? $_GET['page'] : 'SEO-Home-Page-with-nice-keywords';
  
  switch ($nav)
  {
      case 'SEO-Home-Page-with-nice-keywords':
?>
<!-- BREAK OUT OF PHP TO ENTER HTML --> 
<H1>HOME</H1> 
<!-- RETURN TO PHP --> 
<?php
      break;
      
      case 'SEO-About-Page-with-nice-keywords':
?>
<!-- BREAK OUT OF PHP TO ENTER HTML --> 
<H1>ABOUT</H1> 
<!-- RETURN TO PHP --> 
<?php
      break;
      
      default:
          header('HTTP/1.1 404 Not Found');
          exit;
          // Or use some type of 404 page
  }

Thanks for the solutions provided, mgraphic, your solution seems interesting, I hope you would not mind me asking you to explain it to me just a little.
Why would I try and use $_GET to look for a query string, when the <a> tag does not parse a query string, am I being totally stupid here.
Please lead the blind here.

The rewrite rule in the htaccess is appending uri parameters and this happens before the php parser begins.

RewriteRule ^([A-Za-z0-9-_]+)$ index.php?page=$1 [QSA,L]

Thanks mgraphic, that is working great now.
Could I bother you for one last problem though

The issue I am having now is that google has my page indexed as http://www.example.com/index.php?page=About_Us NOTE THE UNDERSCORE

Now I have changed all these URL's to have hyphens inbetween

when I click on that google link it takes me to my site but the contents of the page is invisible because it is asking for About_Us, if I alter it to About-Us it shows but how do I make it do that by itself.

Page is php - put in a header call to the correct link

use str_replace

Will str_replace work as far as google is concerned. I mean will the url in the browser alter from
example.com/index.php?page=About_Us
to
example.com/index.php?page=About-Us
OR to
example.com/About-Us

If you redirect. Yes.

If you get the appropriate page content from the database. Yes.