SiAlON ceramics, solid solutions based on the Si$3$N$4$ structure, are important, lightweight structural materials with intrinsically high strength, high hardness, and high thermal and chemical stability. Described by the chemical formula β-SiAlON, from a compositional viewpoint, these materials can be regarded as solid solutions between Si$3$N$4$ and Al$3$O$3$N. A key aspect of the structural evolution with increasing Al and O ($z$ in the formula) is to understand how these elements are distributed on the β-Si$3$N$4$ framework. The average and local structural evolution of highly phase-pure samples of β-SiAlON with $z$ = 0.050, 0.075, and 0.125 are studied here, using a combination of X-ray diffraction, NMR studies, and density functional theory calculations. Synchrotron X-ray diffraction establishes sample purity and indicates subtle changes in the average structure with increasing Al content in these compounds. Solid-state magic-angle-spinning $\mathrm{<mrow\; data-mjx-texclass="ORD">27</mrow>}$Al NMR experiments, coupled with detailed ab initio calculations of NMR spectra of Al in different AlON tetrahedra (0 ≤ $q$ ≤ 4), reveal a tendency of Al and O to cluster in these materials. Independently, the calculations suggest an energetic preference for Al-O bond formation, instead of a random distribution, in the β-SiAlON system.