If you aren't using some kind of custom Authentication it is already
taken care of. The Permissions to create or read a MySite are given to
NTAuthority/AuthenticatedUsers. That means anyone who is authenticated
via AD will have permission to see MySites.

I am having a few users  report they are unable to see the MySite link
except in areas they have specifically been granted higher rights
(Sites they own). We are using AD to authenticate users.

You need to check the Personalization Service Permissions on your Shared
Services Provider. This is where the permissions are set for who can
and who cannot see the MySite link. The default is to have
NTAuthority/Authenticated users  have Personal Features and Personal
Sites permissions. These permissions are what govern whether you see a
MySite link or not. If users aren't authenticating via AD, if they are
accessing the site anonymously, or if these rights have been changed
from the default setting then they won't see the MySite link.

I tested this be creating a user and giving them ReadOnly access  to a
SharePoint MOSS site. They still have the MySite link. If I remove the
Personalization Service Permission refrerence above the link goes away.

Where would I find  "Personalization Service Permission"?

Go to Central Administration. Click on the SharedServicesProvider that
is Hosting your MySites in the LeftHand Navbar. You will see
Personalization Services Permissions in the User Profiles and MySites
section of the Interface.

When I got to: Central Administration

All I see on the left is:

Links to related administration home pages

-Windows SharePoint Services

-SharePoint Portal Server

Neither of these has any mention of mySite or shared services.
??

I didn't read the Subject line well enough. I was describing
Central Admin for SharePoint 2007, not 2003. I don't remember anymore
where these settings would have been in 2003. It operated in a
completely different way.