I didn't have a song in my last relationship, mostly because it didn't last long enough. Kind of "Sing Me Spanish Techno" but that was just because it was kind of a joke between us.
Before that though, it was less a song and more everything by the Decemberists. It's kind of a shame, I've had a hard time listening to them since then. Plus tastes have changed since then, so not totally the relationships fault.