Results are reported from a search for a class of composite dark matter models with feeble, long-range interactions with normal matter. We search for impulses arising from passing dark matter particles by monitoring the mechanical motion of an optically levitated nanogram mass over the course of several days. Assuming such particles constitute the dominant component of dark matter, this search places upper limits on their interaction with neutrons of $alpha_n leq 1.2 times 10^{-7}$ at 95% confidence for dark matter masses between 1--10 TeV and mediator masses $m_phi leq 0.1$ eV. Due to the large enhancement of the cross-section for dark matter to coherently scatter from a nanogram mass ($sim 10^{29}$ times that for a single neutron) and the ability to detect momentum transfers as small as $sim$200 MeV/c, these results provide sensitivity to certain classes of composite dark matter models that substantially exceeds existing searches, including those employing kg-scale or ton-scale targets. Extensions of these techniques can enable directionally-sensitive searches for a broad class of previously inaccessible heavy dark matter candidates.