The expression seems to come from the late 19th/early 19th century when it was "to sing from the same hymnal"
The idea was that if two people had different hymnals then they would be of different religions/sects and thus disagree on fundamental [religious] issues.
I found this snippet (in a business context) from 1922 in Google Books:
Reclamation Era - Page 317
Students of Main Street might surmise that Davis and I did not sing from the same hymnal. Such a surmise would be correct.
Hymnal was later replaced by hymnbook, then hymnsheet, and then simply "sheet"- and eventually page and, with the idea of singing diminishing, "being on the same page."
Thus to be on the same sheet as someone was to share their ideas, ideals, and beliefs.
I did find earlier references to singing from the same hymnal but these tend to be literal and imply, rather than state, a unity within one sect/religion.