What gives them the right? Laws about unregistered marks are derived from a way-old English business principle: if someone attracts customers (goodwill) it is unfair for someone else to falsely pass off products or services with a similar trademark, thereby confusing consumers. Sometimes these state or federal laws are referred to as unfair competition laws, or unfair business practices. Famous unregistered trademarks can be protected under federal dilution laws. (Note, some functioning regional trademarks may not qualify for registration because they are not used in commerce regulated by the federal government -- typically, interstate commerce.)
The registration process. Some people believe that registration is the process of turning a name into a trademark. Actually, it's the opposite. You can't get a registration unless the name already is a trademark. Once your examiner is satisfied that you have a trademark, registration is granted and that enhances your already-existing trademark rights. Registration gives the owner a presumption of ownership, provides constructive notice to other companies in the U.S., and offers the hope of incontestability (after a few years). Registration may also increase your payment in case of a willful infringement.
The unregistered trademark. As noted, an unregistered first user of a trademark can often claim trademark rights within the geographic selling area. But keep in mind that having an unregistered name is not the same as having an unregistered trademark. You can't claim trademark rights, unless the moniker meets the legal requirements of a trademark -- that is it's distinctive and associated with your goods and services.
The way it is. All that said, nowadays, the tendency is to register as much as possible. That's partially attributable to the Internet: registration helps in domain name battles and the Internet has made made many regional (previously local unregistered) trademarks into national businesses. In addition, registration is now de rigueur for startups whose equity investors perceive it as adding value.