High-Energy neutrinos from the annihilations of dark matter captured within the Sun is thought to be a relatively clean, indirect probe of dark matter physics. In addition, this probe is sensitive to the dark matter-proton cross section so it can be used to cross-check direct searches, and does not rely on a large annihilation cross section in order to be observed in near-term experiments such as IceCube. I will consider a modification of the standard scenario. Dark matter that interacts strongly with itself as has been proposed in several contexts. I show that viable models of self-interacting dark matter can lead to large boosts in the expected neutrino flux from the Sun, though not from the Earth and not in direct detection. Thus an anomalously large neutrino flux from the Sun is a signpost of self-interacting dark matter. I will also consider the consequences of a significant dark matter self-interaction for other indirect dark matter searches, such as high energy gamma-rays or neutrinos from the Galactic Center. Time permitting, I will describe some additional interesting possibilities. First, I will discuss the possibility that the high-energy neutrino signal from the Sun may reveal the presence of substructure in the dark matter halo at the solar radius and possibilities for indirect signatures of particle dark matter in stars other than the Sun.