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 a(n) <= 1.2 x 10(-7) at 95% confidence for dark matter masses between 1 and 10 TeV and mediator masses m(phi) <= 0.1 eV. Because of the large enhancement of the cross section for dark matter to coherently scatter from a nanogram mass (similar to 10(29) times that for a single neutron) and the ability to detect momentum transfers as small as similar to 200 MeV/c, these results provide sensitivity to certain classes of composite dark matter models that substantially exceeds existing searches, including those employing kilogram- or ton-scale targets. Extensions of these techniques can enable directionally sensitive searches for a broad class of previously inaccessible heavy dark matter candidates.