Load cell setup, weight deviates to much in time

[jremington]

Can it be that the power supply has a non-constant voltage? Is there a way to get a more constant supply?

Yes and yes. Use a precision voltage reference for the bridge.

Please describe the rest of your circuit.