Dark matter candidates with masses around the Planck-scale are theoretically well-motivated, and it has been suggested that it might be possible to search for dark matter solely via gravitational interactions in this mass range. In this work, we explore the pathway towards searching for dark matter candidates with masses around the Planck-scale using mechanical sensors while considering realistic experimental constraints, and develop analysis techniques needed to conduct such searches. These dark matter particles are expected to leave tracks as their signature in mechanical sensor arrays, and we show that we can effectively search for such tracks using statistical approaches to track-finding. We analyze a range of possible experimental setups and compute sensitivity projections for searches for ultraheavy dark matter coupling to the Standard Model via long-range forces. We find that while a search for Planck-scale dark matter purely via gravitational couplings would be exceedingly difficult, requiring ∼80dB of quantum noise reduction with a 1003 array of devices, there is a wide range of currently unexplored dark matter candidates which can be searched for with already existing or near-term experimental platforms.