Randall was born August 1, 1926, in Clinton, Custer and Washita County, Oklahoma. She was known informally as Gene, which was derived from her birth name, Genevieve. Randall's father, Charles Patrick Roberts (1892-1980), originated from Texas and by 1900, his family moved into Chickasaw Nation, Indian Territory, to farm while Charles was young. The family moved to Seminole, Seminole County, Oklahoma by 1930 where he worked as a garage mechanic then to Shawnee, Pottawatomie County, Oklahoma, where he worked as a construction laborer. The family lived in Shawnee until the start of World War II.