The computation is based of the Honda-Tate theorem which states that isogeny classes of abelian varieties over finite fields are completely determined by the characteristic polynomial of their Frobenius automorphism acting on the first $\ell$-adic cohomology group. For a given dimension $g$ and base field of size $q$, a complete list of all Weil polynomials that do occur can be enumerated using a technique described in an arxiv preprint of Kedlaya's. In 2016, Dupuy, Kedlaya, Roe and Vincent improved upon Kedlaya's original code to generate these tables and the data they contain.

One may also with to see this paper by Kedlaya and Sutherland, where these techniques are used to compute Weil polynomials for K3 surfaces.