[bshimmin]

I am pretty sure the term comes from "relationship" - I remember it being used in alt.tv.x-files about Mulder and Scully, though I don't know if that was its first use (their relationship was/is very much as you describe): certainly people who wanted the two to get together were known as "shippers".