I just completed redeisgn of an existing site. The new site has completely different file names than the previous version. Google says use a 404 error page with info about the new site and links to new pages.

What should I do about other websites (not Search Engines) linking to pages which no longer exist in my new site. Should I do a redirect to just let the 404 do its job?

301 redirect

if the old page was a xxx.htm and the new page is php how do I set up a 301 in html?

This is not necessarily the proper syntax for your server.

RedirectMatch permanent oldpage.html newpage.php

All you do is say send the oldpage to the newpage and this change is permanent (301)

Can I have a specific example on a 301 redirect. I'm fairly new at this.

.HTACCESS redirect:

Options +FollowSymlinks
RewriteEngine on
rewritecond %{http_host} ^domain.com [nc]
rewriterule ^(.*)$ http://www.domain.com/$1 [r=301,nc]

http://www.webconfs.com/how-to-redirect-a-webpage.php

I gave it to you in one format

RedirectMatch permanent oldpage.html newpage.php

And the monkey gave it to you in another. One of the two will work for you.

Alternatively a general "This page doesn't no longer exist... please visit our sitemap for more information" could be the better solution. At least it will save you much time especially on complex websites with dozens of pages.

Definitely do a 301 redirect. If the content is valuable and you want search traffic from it, a 404 just won't do. Google will forget about that page and move on. Tell Google (especially if it has indexed the page that serves the 404) that your content has moved to another location.

Can I have a specific example on a 301 redirect. I'm fairly new at this.

Sure, tell us what server technology you use and we'll be able to give you the right one.