Adam's circuit works, but it is overly complicated and requires a floating supply of 0.5V.
An op amp can sum 2 signals and multiply by a constant all at once. This is done by a summing amplifier.
Here is the summing amplifier configuration:
The gain of a non-inverting amp is (1 + Rf / Rg)
And, if we make Rin1 = Rin2, the input at the + input is (in1 + in2) / 2
So, if we make in1 your sensor output (-0.5V to 0.5V) and make in2 0.5V, we get
out = (in1 + 0.5V) / 2 * (1 + Rf / Rg)
We want the output to be 0 to 5V. The minimum of (in1 + 0.5V) / 2 is 0, so that is okay, no offset is needed.
The max of (in1 + 0.5V) / 2 is 0.5V and we want this to come out at 5V, so the gain must be 10.
From the gain equation:
(1 + Rf / Rg) = 10
Rf / Rg = 9
So, choose 90K for Rf and 10K for Rg to get a gain of 10.
Now all we need to do is connect in2 to 0.5V through Rin1.
We can choose any resistance for Rin1 and Rin2 (though they must be the same). I will choose 10K for these.
Now, assuming we have a well regulated supply voltage, all we have to do is find a voltage divider that outputs 0.5V from the supply voltage through a resistance of 10K. Thevenin's theorem allows us to do this.
We have two equations that will determine R1 and R2.
The first says that the ratio of R2 to (R1+R2) is the same as the ratio of the output (0.5V) to the input (V):
R2 / (R1 + R2) = 0.5 / V
Flipping both sides:
(R1 + R2) / R2 = V / 0.5 = 2 * V
R1 + R2 = 2 * V * R2
R1 = (2 * V - 1) R2
The second equation states that the parallel combination of R1 and R2 must be 10K:
1 / R1 + 1 / R2 = 1 / 10000
Substituting for R1 from the other equation:
1 / ((2 * V - 1) R2) + 1 / R2) = 1 / 10000
(1 + (1 / (2 * V - 1)) / R2 = 1 /10000
R2 / (1 + (1 / 2 * V - 1)) = 10000
R2 = 10000 * (1 + 1 / (2 * V - 1))
So, if, for example, V is 10:
R2 = 10000 * (1 + 1 / 19) = 10526
And from the equation solved for R1 above:
R1 = (2 * 10 - 1) * 10526 = 199994
So, now the circuit looks like this: