It is the Improbability Drive that picked them up. As Trillian tells Zaphod when they pick up Ford and Arthur in THHGTG:
"Improbability Drive," she said patiently. "You explained it to me yourself. We pass through every point in the Universe, you know that."
So every point in the universe can be anywhere/anywhen in time-space. As evilsoup pointed out, it is just very very improbable (i.e. piece of cake for the Heart of Gold).
Also, note that in the Wikipedia entry Technology in The Hitchhiker's Guide to the Galaxy it is noted that:
Karey Kirkpatrick, who with Adams (before his death) adapted the novel for the screen in 2005, described the improbability drive as a "plot contrivance machine", allowing Adams to construct elaborate plotlines based on coincidences that would, in other narratives, be considered too improbable to be believed.
