> what state the SSN-holder was actually born

No, it was the state where the SSN was issued. Not all children applied for an SSN at birth. Centralization of SS offices also altered this practice.

See, e.g., http://www.ssa.gov/history/ssn/geocard.html