The hyperfine structure of the interstitial muonium (Mu) in rutile (TiO$_2$, weakly $n$-type) has been identified by means of a muon spin rotation technique. The angle-resolved hyperfine parameters exhibit a tetragonal anisotropy within the $ab$ plane and axial anisotropy with respect to the $langle 001rangle$ ($hat{c}$) axis. This strongly suggests that the Mu is bound to O (forming an OH bond) at an off-center site within a channel along the $hat{c}$ axis, while the unpaired Mu electron is localized around the neighboring Ti site. The hyperfine parameters are quantitatively explained by a model that considers spin polarization of the unpaired electron at both the Ti and O sites, providing evidence for the formation of Mu as a Ti-O-Mu complex paramagnetic state. The disappearance of the Mu signal above $sim$10 K suggests that the energy necessary for the promotion of the unpaired electron to the conduction band by thermal activation is of the order of $10^1$ meV. These observations suggest that, while the electronic structure of Mu (and hence H) differs considerably from that of the conventional shallow level donor described by the effective mass model, Mu supplies a loosely bound electron, and thus, serves as a donor in rutile.