We report theoretical results for the stability of half-quantum vortices (HQVs) in the superfluid phases of $^3$He confined in highly anisotropic Nafen aerogel. Superfluidity of $^3$He confined in Nafen is the realization of a nematic superfluid with Cooper pairs condensed into a single p-wave orbital aligned along the anisotropy axis of the Nafen aerogel. In addition to the nematic phase, we predict a second chiral phase that onsets at a lower transition temperature. This chiral phase spontaneously breaks time-reversal symmetry and is a topological superfluid. Both superfluid phases are equal-spin pairing condensates that host arrays of HQVs as equilibrium states of rotating superfluid $^3$He. We present results for the structure of HQVs, including magnetic and topological signatures of HQVs in both the nematic and chiral phases of $^3$He-Nafen.