“how did they figure that out without direct observation over hundreds or thousands of years?”
The interesting thing is that back in 9100 BC - which is how they arrived at this date - Sirius barely clears the horizon at Gozeli Tepe. Prior to 9100 BC, the precession of the equinoxes is so significant that Sirius actually does not rise over the horizon at Gozeli Tepe. Today, Orion would rise as much East as South - back then it would rise due South.
If a totally new star that was unfamiliar to you and to the society suddenly appeared just over the horizon - this would be a significant event. Especially with it being so bright, even on the horizon.
For the life of me, I can't remember the name of the book, but it starts out with a cry echoing across the Andes because a star that was supposed to rise didn't.