How did Airbus fit 6,340 gallons more fuel into the A359?
Bloomberg says minor changes to "piping and venting" made the capacity available. It came from previously unused space in the center fuel tank.   


The a359 center tank filling point is not at the highest point in the tank, so it needs a vent in order to use that space. Without the vent, the tank airlocks and no more fuel will flow in. 
Piping refers to changes to that tank's inerting system, designed to prevent explosion of fuel vapor in the tank. Inerting has been required for wingbox center tanks ever since TWA800. See Leeham for more detail, search the page for Update2.


As to why this is not part of every a359, it is operating cost. The regional variant has a 260t MTOW and therefore lower landing and navigation fees. The 280t MTOW needed for the ULR will be available from 2020 on the standard model, so there is very little difference otherwise. If you order the ULR you can paper change it to a regional, though I don't know anyone who would. 

Leeham also has an interesting article on how seating (passenger weight) has to be limited to get maximum range from the ULR.