The "prose Edda", as opposed to the "poetic Edda" was written in the 13th century by Snorri Sturlusson as we know.
The older, poetic Edda is much older.
How old could it actually be? There seems to be a possibility there is a linguistic connection with the name "Veda" - the old Indian Vedas - which would suggest it is really very, very old.
Properly, the name Edda refers only to one work: Snorri's Edda, a work on Norse poetics, including the background in mythology necessary to write and understand such. The name probably comes from an Icelandic word for (great) grandmother, but there are also other theories.
The so-called Poetic Edda, also known as Sæmundar Edda (from Sæmund the Learned) or the Elder Edda, is a modern construct. 17th century Icelandic Scholars knew Snorri's Edda, and speculated that he had used an older collection of poetry when writing his book. When bishop Brynjólfur Sveinsson got into his possesion a manuscript containing a collection of poetry dealing with different mythological and legendary matters, he was sure he had found that Edda. The manuscript was sent to the Danish King, and is today known as the Codex Regius (Bishop Brynjólfur also secured Flateyjarbók for posterity).
Today, the name The poetic Edda is seen as the preferable one (it was almost certainly not compiled by Sæmund), and is commonly used. Modern editions often add poetry discovered in other sources apart from the Codex Regius. Thus, both the name and the exact contents are modern conventions.
As for the age of the poetry itself, it is really impossible to say. The poetry was likely orally transmitted during long periods, with a relatively stable core being improvised on or having small changes. This is evidenced by Völuspá, where we have two full length versions as well as fragments given by Snorri: they differ in which order they present some matters, have differing passages, and one seem to have had a Christian message attached to it. Some parts are identical, however. We can see that some passages has older grammar or word choices, but this does not help to date the work in it's entirety. One passage can also be found in a 9th century German source, but that is as far back as we can really be sure.
Veda seems to stem form a PIE word for "knowledge". According to Etymology Online, it's closest cognate in North Germanic languages today is Swedish "veta" (surprisingly close), which stems from Old Norse vita, according to SAOB. Thus, there does not seem to be any substantial link here.
You should be able to verify the first three paragraphs in any half-way decent intoduction to a modern edition of at least the poetic Edda. I have used Lars Lönnroth's translation Den poetiska Eddan and Karl G. Johansson's and Mats Malm's Snorres Edda. Lönnroth has also supplied the argument in the fourth paragraph.
