Load Cell DAQ via Arduino Mega

You should have a bypass capacitor across the power input (100uF/10V in parallel with 0.1uF ceramic will do), 10n input caps on each input line, as Andy suggests, with series resistors, and I would also suggest a 10n capacitor from reference output to ground.

If the Ardno and INA125 are separated by more than a few inches, a resistor of at least 1 K on the output of the INA125 and another capacitor from the Ardno input to ground.

A few things to be aware of first: With only 10 bits your 1 bit resolution will be (Full Range)/1023, in this case 40kg/1023 = 0.0391kg (39.1g). The 1 bit noise level (39.1g) at the Arduino analog input is 5v/1023 = 4.89mv, (assuming a 5v Arduino system). At the amplifier input the 1 bit voltage value is further divided by the amplifier gain. So any system noise over these values will reduce your resolution further unless extra filtering is used. Also remember that the Arduino chip can be damaged if the A0 input goes below GND or over VCC. Protection diodes could help here if there is no other control.

The +10 and -10 supply setup only helps if needed by the amplifier chip, and/or if it brings the voltage across each load cell to the max 10v level, thereby giving the max output. But as above this could also lead to a negative voltage on A0. For example with a +- supply just lifting your system up by the weighing platform might send A0 negative. (If you do test for this be sure to disconnect A0 from the Arduino first.)

To filter the S+ and S- lines you could try placing low value series resistors onto each line then placing a parallel cap (non-polarized) across them, (with the cap nearer to the amplifier chip). 1k resistors and a 1uf cap might be good values to try. A same value series resistor and cap to GND on the A0 line may also help, (with the cap nearer the Arduino input). These filtering ideas might not help much if your system noise is already too high. The extra RC parts will reduce the response time slightly. If the slower response is unacceptable then a lot of digital filtering would be needed.

Check your zero point noise. Short S+ and S- and see if you get a stable reading near zero. (Do this first by disconnecting A0 and verify with a DVM that A0 does not go negative.) With A0 connected, any "bouncing" you see will likely be system noise from the amplifier or the Arduino. To reduce amplifier noise place larger value caps from the V+ pin to GND and from the V- pin to GND. (10uf to 47uf should do, observe correct polarity). A small cap (maybe 0.1uf) across the gain resistor might help, (check the amplifier's data sheet). To reduce Arduino noise be sure you are using the analog function that switches off the digital system before taking a reading. I don't know if the standard analogRead does this or not. Most of the Atmel chips have this capability. You may need to look up the library function and read through the Atmel chip data book.

To calibrate your system use a good resolution DVM. Temporarily disconnect the A0 input and connect it to the DVM +, with DVM - to GND (or E-). Place a full range mass (40kg) on the scale, adjust Rgain (add a small potentiometer if needed) until you get a reading very close to, but not over Vref. Next remove the 40kg mass and see if the voltage reading is very near 0v. If not near 0v you can give some voltage offset by adding a very high value potentiometer (100k to 1M) connected between E+ and E- with the center connected to a 100k then to S+ or S-. After adjusting the zero point retest and readjust Rgain if needed.