I'm curious where this comes from, is it written law somewhere? Where is this right defined?
It's normally written as "we reserve the right to refuse service to anyone" in restaurants or other businesses and it's known to be a legal statement unless the entity is discriminating guests.
In which countries (I guess mostly USA) does it even apply?
Well right off the bat, let me say that the signs are legally irrelevant. Restaurants that do or do not have the signs have the same rights, regardless of whether they telegraph that to their costumers. As an analogy, homes without "No Trespassing" signs have just as much right to call the cops on trespassers. The main purpose of the signs is not to reserve any rights, but to give owners something to point to when unruly customers don't want to leave.
In the United States, very few rights are explicitly laid out and protected. So if you're asking if there's a specific law or statute saying "Businesses can deny customers," the answer is that it doesn't exist. Basically, the "right" to refuse customers exists for the same reason that the right to smoke cigarettes exists: because there are no laws against doing so. I guess if you want to get philosophical, the right to refuse service is an extension of the restaurant's right to property, and its right to control that property. A restaurant that is legally required to sell its products away doesn't "own" its products or facilities in any meaningful way.
But like smoking cigarettes, the right to refuse service in the United States is not absolute and can be infringed upon by legislatures with good reason. The Civil Rights Act of 1964 forbids public accommodations such as restaurants from discriminating based on race, color, religion, sex or national origin. Later federal legislation added protections for disability, age, pregnancy, and veteran status. Additional protected classes vary by state. In particular, many states add sexuality or gender identity to the list, and California's proscription of discrimination based on "personal attributes" covers basically anything a clever attorney can dream of.
How much of this applies in other countries, I'm not sure. But I'm skeptical that there would be a country where businesses are legally required to seat even unruly customers.
If X does not have a right to refuse to serve Y, that would imply that Y can legitimately compel X to provide service. In the absence of a particular reason why Y should be legitimately able to compel the service of X, the "right to refuse service" would thus exist as default and doesn't need to "come from" anywhere.
To complete TenthJustice's excellent answer, let me say that in other (liberal democratic) countries, things may be different. In France, which tends to have many more laws regulating many more aspects of life, it is forbidden for a restaurant or any professional selling goods or service to refuse to sell the good or perform the service to any customer. The law says:
Il est interdit de refuser à un consommateur la vente d'un produit ou la prestation d'un service (article L. 121-11 du code de la consommation)
that is
It is forbidden to refuse the selling of a product or of a service to a consumer.
If you do that you risk a fine of Euro 1500 personally, and your entreprise a fine of Euro 7500. When it is determined that the race, religion, etc. of the consumer was the reason of the refusal, sanctions may be heavier.
That message was conceived after the Civil Rights Act was passed in 1964. Prior, Jim Crow openly permitted discrimination, allowing for "whites only" signs to be posted and legally enforced. In Colorado, such signs are illegal because they have historically been used for discriminating (see last 2 pages).
