This paper aims to study the magneto-plasmons in an anisotropic graphene nano-waveguide with bi-gyrotropic cover and substrate. The substrate is backed by a perfect electromagnetic conductor (PEMC) layer, a general and ideal boundary, which can be transformed easily into the perfect electric conductor (PEC) or the perfect magnetic conductor (PMC) boundaries. The upper and bottom layers of the graphene sheet are made of different magnetic materials, each one has the permittivity and permeability tensors of and, respectively. The external magnetic field is applied perpendicularly to the structure surface, which can be provided by a permanent magnet placed underneath the ground plane. Hence, the graphene sheet has anisotropic conductivity tensor (). A novel analytical model has been proposed for the general nano-waveguide to find its propagation properties. As special cases of the proposed general structure, two important new waveguides have been introduced and studied to show, first the richness of the proposed general nano-waveguide regarding the related specific plasmonic wave phenomena and effects, and second the validity and the high accuracy of the proposed model. The analytical and the simulation results are in an excellent agreement. It is shown that the modal properties of the proposed structure can be tuned effectively via the external magnetic field and the chemical potential of the graphene. Harnessing the non-reciprocity effect of anisotropic materials and the graphene sheet, the presented analytical model can be exploited to design tunable innovative devices in THz frequencies.