Their relationship first started in A Flight to Remember when Amy tells her parents that she is dating Fry, and starts to have a relationship with both Leela and Amy. The relationship ended when Leo and Inez find Amy a new boyfriend, a green squishy boy.
Their relationship continued in Put Your Head on My Shoulder when Fry asks Leela to go out with her, but refuses. So he goes with Amy to Mercury. They have a lot of fuel-consuming fun with the new car and run out of fuel in a desolate area, where they are stuck for a few hours. They get into talking and realize they have a lot in common, and they end up sleeping with each other. Their relationship doesn't last long when Fry's head gets attached to Amy's body and she sees someone else (Gary).
Also, in Parasites Lost, Fry pulls out a baggie of massage oil and offers to give him the massage he used to give Amy (though, this wasn't shown in any previous episodes).
Amy: So while they're towin' us, you wanna do it?
- Episodes where their actions between these characters based on the event, as well as references by other characters.