I won't comment on the circuit design, as that seems to be getting plenty of attention, but I built a project where I hacked a bathroom scale so it was network enabled and has a web server to to serve the current weight, and I have a few thoughts on putting the whole thing together.
Before you build your amp, in order to get a rough idea of how to set the gain, build the strain gauge circuit first, power it up, and use a multimeter (which is much more sensitive than your Arduino's ADCs) to measure the output voltage from your strain gauge circuit with the maximum expected load applied. Then when you build your amplifier circuit you can select gain resistors that bring the amp's maximum output to 5V (the Arduino's ADCs sample 0-5V), and you will get the most range out of your ADC.
The reason to do this is that the range and resolution of the ADCs is limited and discreet, so if you want to measure 0-1000 pounds, with the 10-bit resolution of the AVR's ADCs, you would at best be accurate to within a pound if your amp's output signal goes from 0-5V as the weight increases from 0-1000 lbs. If you just half-ass it or guess with the gain resistors, or start with pure trial-and-error and get bored and don't use the full range, you will throw away accuracy. Say you cobble together an amp and it only puts out 0-2.5V, then you will be throwing away half the range and only accurate to within 2 lbs. for that same 1000 lb. range.
It depends on the project and how much you care though. When I built my hacked scale I needed a range of 0-200lbs., but I wasn't very concerned with accuracy. Basically my goal was to determine whether a container on the scale was empty or full, with maybe a very low resolution beyond that like 1/8 full, 3/4 full, that kind of thing. I just built the simplest single opamp differential amplifier circuit I could find with the first low-voltage opamp I had in my parts bag, with the gain set so that it saturates the ADC at ~200 lbs. Even with this super-simple construction it is surprisingly accurate and linear, certainly good to the pound (it's considerably better than that but I didn't even need lb. accuracy so when I calibrated it I added weight in 5 lb. increments to build my table of calibration data).
Schematic added by request:

This is more-or-less the schematic for the circuit I built, but I put it together on a solderless breadboard so hopefully there wasn't too much field engineering in what I actually have working. The deleted part was an extra resistor and potentiometer that was supposed to be able to tune the strain gauge circuit so the output was exactly 0v with no load, but I ended up with a very slight positive voltage no matter what I did, and it wasn't significant so I didn't bother to debug it. Sig+/Sig- are where the strain gauges are wired to the amp circuit. I didn't build my strain gauge circuit, I used the scale, so I actually don't feel that knowledgable about the details of working with strain gauges, I just figured out how to use what was there. Mine had two pairs of gauges, and each pair had a V+, V- and signal wire. I wired the signal line from each pair to either Sig+ or Sig-, and then to power the gauges I wired the power from one pair and the ground from the other pair to V+ and the ground from one pair and power from the other pair to V-.
The resistor values in my circuit don't necessarily mean anything to you, because they were chosen to give the gain I need. Choose yours according to your needs.