The excess voltage is a voltage drop across the regulator.
Take a 12 V circuit, with a battery, a bulb and a switch. The switch is on or off. When the switch in on there is no voltage drop across the switch, and the bulb has 12 V across it and it lights. When the switch is off, the voltage across the switch is 12 V, so none is left across the bulb.
Now put a variable resistor instead of the switch. When there is a lot of resistance it is like a switch that is off, so there is 12 V across the resistor and none across the bulb. When there is no resistance it like a switch that is on, with no voltage across the resistor and the 12 V across the bulb.
So far, it is just like a switch. However, if you put some resistance in the way, there will be some voltage across the resistor and some across the bulb. You could adjust the resistor to get 9 V on the bulb, and there will be 3 V across the resistor. You can change the resistor to get any voltage you want on the bulb.
That is all that a linear regulator is doing, just automatically. It adjusts its resistance to give you the correct output voltage.
If you have a 7805 fed from a 15 V supply, there will be 10 V drop across the regulator.
The power loss in the regulator is the 10 V drop multiplied by the load current. If there is no load, no power is lost. If there is a 0.1 A load, the power loss is 10 V * 0.1 A = 1 Watt which is lost as heat in the regulator.