When was Homer's Odyssey written?
The answer to your question is explored in depth in Bernard Knox's introduction to Robert Fagles's translation. According to Professor Knox, the earliest examples of Greek writing go back to around 725-675 BCE, and that is believed to be the time of that The Iliad was committed to writing. The Odyssey is believed to have been composed sometime later.
The most reliable theory, according to Knox, is that the poem was composed orally, and over an extended period of time committed to writing.
As to the argument that Homer simply strung together a collection of ancient tales, Professor Knox debunks that theory. The structure of the poem is too sophistocated, particularly in terms of chronology, to have been a compilation.
So to answer your question briefly, you could safely say, as Gbeatty suggests below, the seventh or eighth century BCE. It was originally performed entirely from memory, and that the written text probably evolved over considerable period of time.
Since the answers so far were good, I would just like to add a few things about the oral nature of poetry. Some people might believe that Homer's Iliad an Odyssey are too long for there to be any accurate transmission from oral poetry to written language. This is a reasonable assumption when you consider the length of these poems, but a scholar by the name of Milman Parry was able to prove that oral poetry could be recited from generation to generation from memory. He made his case from studying Slavic bards that recounted their tales. So, if Milman Parry is correct, much of Homer could have been preserved in oral form before it was committed to writing, probably sometime in the 700s.
Ah, but what do you mean by "written"?
To expand on that a bit, Homer's version was composed during his lifetime, which was the seventh or eighth century BC.
However, versions of the story circulated for some time before that, and some scholars think he didn't write the poem as much as he simply compiled a single version from oral folk transmission.
What's more, some ancient traditions held that Homer was blind, which would have meant he composed orally and that his poem was written down by someone else.