How do you rig a character made out of linked parts?
You should be able to use the mirror modifier here.

It has an option for mirroring vertex weights.

It uses the standard mirroring name convention (like bones, so it works fine with rigging). Basically if a vertex has weight 0.6 in group.L, its mirrored copy will instead have a weight of 0.6 in group.R. By creating empty groups for the mirrored side it is quite easy to rig one side and have it cleanly mirrored.