I starting dating my SO while I was getting my MA and she was working on her BA. I tried to be honest and up front about my educational goals and priorities. I was actually in the process of applying to PhDs at the time (none within 1500 miles of where we currently are). I fell head-over-heels for her, so I switched to a different (and better) MA program, then took this last year off of school while I applied to PhD programs again (completely different schools than before, and I'm so glad that I waited those two years to figure out what I really want to do).
I drew up a list of programs based on my academic and geographic preferences, then gave her veto power. We don't have much money these days, paying my loans and her tuition, so I ended up only applying to 4 schools in places that we'd both want to live. I'm pretty lucky in that my SO doesn't have any firm plans, and is up for the adventure.
My SO finishes her BA in August, and the next day I'm heading to the University of Hawaii at Manoa (unless my Alternate status changes on my Fulbright application to Romania, in which case SO is totally not going to miss out on a year in Transylvania). She needs to do some grad work where she can definitely get in to a program (meaning in our current town) in order to either get the kind of job she wants or get into a grad program at UHM. So, she'll be in Texas for at least a year (hopefully not more!) while I get settled into grad life in Honolulu. Not ideal, but we both support each other and believe that these are investments that will really pay off later in our lives.
I've never really tried long distance, and it's going to be a huge adjustment, but it's great hearing that a lot of these situations work out well. Thanks for all the stories!