In a circuit being switched by an NPN transistor, do power supply and input need the same ground?
Yes, you need to connect the 5V and 12V grounds in this circuit in order for the transistor to
switch. Remember there must be a return path for the base current. You cannot
send a signal using only 1 wire.
See above, the emitter needs to use the same ground as the signal source (Arduino) or there is no return path.     
Connect the negative terminal of the bottom battery (assuming you have 8 in series) to the Arduino ground.
"Ground" is just a term for a reference point to measure voltages from in your circuit, you can pick any point, (though it's usually a net connected to the negative terminal of a supply). For example you could call the point the positive terminal connects to in the circuit "ground", and then the "original ground" (the ground as shown in your circuit) would be -12V relative to it. The negative terminal does not mean the voltage is negative, it just tells you which way the current flows.  
(a) R1 is to limit current to the base of the transistor. To calculate the value, we need to know how much current we are switching (i.e. how much the relay needs) and the current gain of the transistor. Lets say we are using a transistor with a current gain of 200, and the relay needs 20mA to switch. Since the current through the base is amplified by the current gain, we know the base current needs to be at least 20mA / 200 = 0.1mA.
The base voltage of a typical bipolar transistor is around 0.7V, so the series resistor (R1) needs to be a maximum of:
(5V - 0.7V) / 0.1mA = 43k&Omega;
As the gain may vary (go from min value in datasheet to be safe) we can pick a 33k&Omega; to have some base current to spare. Note that to be an effective switch we want the transistor to saturate, as effective gain starts to drop at the knee between linear and saturation mode (as mentioned by Shokran). So we pick a resistor of a lower value than calculated to make sure we can pull the collector near ground. In cases with e.g. power transistors where minimising dissipation is important it is wise to pick a value of at least 5 times less than calculated (or assume gain of ~20) so we could go as low as 4.3k in the above example.       

(b) R2 is there to make sure the base is pulled to ground when drive current is removed. This is to stop leakage current turning the transistor partially on. The value does not need to be too precise, just enough to shunt the leakage current (datasheet) and not too low to steal too much base drive current. 5-10 times the series resistor (or 1k&Omega; to 500k&Omega;) is a rough range to go from. 100k&amp;Omega is a reasonable value for most cases, though I'd go for 330k here as the leakage current should be minimal. If you need to go a lot lower then you have to adjust the series resistor to compensate.
Note that if the Arduino pin is driven to 0V (i.e. set to output and logic 0) then R2 is not really necessary, it's only if the pin is set to High Impedance (i.e. input)
Note 2 - that this is very rarely something to worry about with BJTs (MOSFETs are another matter and definitely do not want to be left floating) If you have a very high gain transistor (esp darlington), a noisy environment, and/or very high temperature (leakage increases with temp) and a very high collector resistor then it may cause issues, but generally the leakage current will be to small to matter.  
Not that I can spot right now (however it is 4:48 in the morning here so my brain may have long since retired, so I reserve the right to have missed something obvious ;-) )