Search engine results getting Error 404-Not found

I just replaced my old site with my new one (ZC) and as expected, when you do a search of any kind for my type of products, your search results (google) are attached to my old site. So of course when you click on the result that is my web site, you get a Error 404-Not found, since the old site does not exist anymore (same web address as new site). I thought when this happens, my "Not found" box would pop up with a message that I put into to redirect them within my site. If not, how do I set this so that people get some kind of message that I am still in business so they don't think I am gone!!

Add this to the .htacess file at the new site:

ErrorDocument 404 /index.php?main_page=page_not_found

That will bring up the Zen Cart page, which is the site map with a little different wording.

RescoCCC:

Add this to the .htacess file at the new site:

ErrorDocument 404 /index.php?main_page=page_not_found

That will bring up the Zen Cart page, which is the site map with a little different wording.

Which .htaccess file, I have Many. There is not one in the root.

Create one with that in it, and drop it in the root.

RescoCCC:

Create one with that in it, and drop it in the root.

I did that and it seems that it only works for certain searches. If you search for a file or product you get my site map as you said. But if your search takes you to a certain page on my site, like About Us, it does not work. It sends you to the Error 404-Not Found