Does all bottled water start by being distilled first, then the
minerals are added back?

I think it depends on the type of bottled water.  Some bottled water
is "bottled at the source" -- the source usually being a natural
spring somewhere.  This type of bottled water contains whatever
minerals happen to be in that particular spring's water, and I don't
think that anything is added or taken away.  There are other kinds of
bottled water that consist mostly of just purified tap water (or in
some cases, just tap water) and I'm not sure if they really do
anything regarding mineral additives in those cases.

It would be way too expensive to distill water and then add back minerals.
The previous comment is correct.  CO2 maybe added to the bubbly stuff.
In Europe there have been some studies that showed that some bottled
waters were less pure than the local tap water.

In Europe most bottled water is Spring water
( in the UK they sensibly ignore the EU directives against passing it
through UV light to kill off bacteria - or at least they used to until
recently )

Coca Cola had a bottled water whose name I've conveniently forgotton,
that was not even distilled, just straight from the mains (probably
Carbon filtered).
It no longer exists )

My father used to be rather involved in that industry, personally I
regard it as a bit of a con - but pretty harmless.

It depends on whether it is defined as "Mineral Water" which can be
water from any route or whether is it "spring water" which must come
from some form of natural underground spring.