Dear Chuck,
that depends - North Rhine Westphalia was put together in 1946 from parts of Rhineland and Westphalia, so you really cannot decide which one to take, if you do not know the exact birthplace. Anyway in 1871 both would have been part of the "Rheinprovinz" - so what about "Rheinprovinz, Preussen, Deutsches Reich" until you find the exact location of birth?
Kind regards - Heike :-)