This paper presents a search for decays of the Higgs boson with a mass of 125 GeV into a pair of new pseudoscalar particles, $H\rightarrow aa$, where one $a$-boson decays into a $b$-quark pair and the other into a muon pair. The search uses 139 fb$^{-1}$ of proton-proton collision data at a center-of-mass energy of $\sqrt{s}=13$ TeV recorded between 2015 and 2018 by the ATLAS experiment at the LHC. A narrow dimuon resonance is searched for in the invariant mass spectrum between 16 GeV and 62 GeV. The largest excess of events above the Standard Model backgrounds is observed at a dimuon invariant mass of 52 GeV and corresponds to a local (global) significance of $3.3 \sigma$ ($1.7 \sigma$). Upper limits at 95% confidence level are placed on the branching ratio of the Higgs boson to the $bb\mu\mu$ final state, $\mathcal{B}(H\rightarrow aa\rightarrow bb\mu\mu)$, and are in the range $\text{(0.2-4.0)} \times 10^{-4}$, depending on the signal mass hypothesis.