Great question!

Most of the Anglo-Saxon poems that survive are from the 10th century or later (including Beowulf), but we do have good hints and clues for what poetry in the 5th century might have sounded like. One poem, the Dream of the Rood, seems to have been written very early (there are a few lines of it on a stone cross that's been dated to the 7th century), and it is written in alliterative verse. Bede also gives us an early poem which he translated from English in Latin in the 730s, and a translation of this poem back into English (which appeared shortly after the latin) is also in alliterative verse, and it seems reasonable to assume that the original (before Bede translated it into latin the first time) was also alliterative. And similar alliterative structures appear in (somewhat later) poetry in Scandinavia. We can't know for sure that this style wasn't, say, invented in the 7th century (and then spread around the North Sea zone to other 'Germanic' people), but it's not crazy to guess that it's older, and that it could have been common in the 5th century.

These poems were almost certainly meant to be accompanied by a lyre (and Beowulf actually describes Hrothgar singing a poem with a lyre). Various styles of lyres were popular around the Greco-Roman world in antiquity, and we've found a few lyres in Europe from late Iron Age celtic sites, but by the late 5th century AD a distinctive style had developed in Northern Europe with 6 strings and a maple (or sometimes oak) body and sound board. We've found a number of examples in graves (mostly dating to the 6th and 7th centuries AD), some of which are very well preserved. My favorite was recently discovered near Trossingen, Germany, and it's in incredibly good condition. Here's a photo of the original, and of a reconstruction, showing an accurate copy of the amazing carving found on the original. Lyres have also been found in famous Anglo-Saxon graves like Sutton Hoo (probably belonging to an Anglian king), Tapplow, and - most recently - the grave of the 'Prittlewell Prince'. There are fragments of lyres in a few other Anglo-Saxon graves (Snape, Bergh Apton, and Abingdon), and Esther Cameron recently told me that several more have been discovered and will soon be published (she was writing up the specialist reports last summer). We've found several other really well preserved lyres in Germany, several of which (from Oberflacht) were sadly destroyed in WWII (but you can find photos if you do a google search). And there was a small lyre in the grave of a young boy in Collogne.

All these lyres, or at least the ones that survived well enough for us to tell, had 6 strings, though there's at least one lyre bridge that's been found that may have been for a 7 string lyre, and I think there's a stone carving of a lyre with 7 strings in Ireland from a slightly later date.

So how would the lyres have been tuned? Many have suggested a pentatonic scale, and this is what Benjamin Bagby chose to do in his performance of Beowulf (which I'll say more about below). This works really well, and has the advantage of being really easy to pick up with little or no expertice and make music that sounds good (you can litterally strum randomly and make music, it's great). We know that lyres could be social instruments (Bede tells a story where a lyre is being passed around a circle of men, and everyone is expected to be able to play a song), so a simple tuning that lends itself to accompanying a voice and requires little operator skill makes a lot of sense. We do, however, have a musical treatise from the 9th century, by an Anglo-Saxon named Hucbald, in which he says that lyres were tuned in a hexachord: C,D,E,F,G,A. That's how I tune my reproduction, and it's very versatile (despite the lack of a 7th note to complete the major scale). But whether or not that scale, or a pentatonic scale - or something else entirely - was used in the late 5th century is impossible to say for sure as no direct evidence survives.

How the lyre be used to accompany a poem like Beowulf is really anyone's guess, but there have been some great - and very different - interpretations proposed by various people (many of whom have helpfully uploaded videos to youtube).

Benjamin Bagby, who's spent his life studying and performing medieval music, has put together a fantastic interpretation of Beowulf (note the multiple links to several recording snippets) using a reproduction of an oak lyre from Oberflacht, Germany. He went with a pentatonic tuning, and uses his lyre to pluck out supporting melodies and fill dramatic pauses in the text. He based his interpretation on oral poetic traditions that are still alive in Africa, and it ends up somewhere between a dramatic reading and a song. He says each performance is half memorized and half improvised - he doesn't have a set 'tune' for the poem so much as a set of melodies and themes that he draws on in response to the music and the crowd, which is the kind of performance we'd expect from a scop performing within an oral tradition. I've heard him perform in person twice, and would definitely recommend purchasing the DVD of the performance if you're at all interested in Anglo-Saxon poetry.

But that's certainly not the only way to interpret this style of poetry. This archaeologist performs Caedmon's Hymn (from Bede), and he plays it in a much more vocally restrained and rhythmic style, strumming chords on the lyre (instead of plucking out individual notes harp-style like Bagby does), and he makes no attempt to sing the words. It's great, and also totally historically plausible. (I'm less sure about when he says Old English poetry is 'deeply pre-Christian' and has pagan undertones - the evidence simply isn't strong enough to confirm or deny what he asserts).

In contrast, music teacher Will Rowan chose to sing the poem 'Deor' entirely as music with no recitation at all. He's using a 7 stringed lyre, but his performance is otherwise also entirely plausible. I think, indeed, that it highlights something important about the poem he's singing, which is how the alliterative meter also has a syllabic rhythm beyond (or beneath) the more obvious alliteration that can only be fully appreciated when sung the way he sings it; Bagby's Beowulf doesn't always capture this lyricism, but it's there in the text of Beowulf as well (there was actually a paper about this at the Leeds IMC conference two summers ago). This, to me, suggests that Will's interpretation may be picking up on something the previous two artists missed about how these poems were originally meant to be performed.

I highly recommend getting your hands on a lyre of your own and trying your own hand at bringing these poems to life - it's incredibly rewarding, and even though it can't ever tell us how these poems were really performed, it does teache you a lot about the wide repertoire of musical expression that a simple instrument like the 6-stringed lyre makes available.

I should also add that, in Anglo-Saxon England, it's probably wrong to imagine a band of warriors gathered in a hall to listen to and sing heroic poems in the 5th century. With very few exceptions, most of the evidence suggests that great halls, and the culture that surrounds them, really took off in England in the 6th century, and reached its height in the 7th at royal sites like Lyminge (Kent) and Yeavering (Northumbria). But halls were common before the 6th century in continental N. Europe, and while most of the lyres we've found in archaeological digs are from the 6th century and after, these halls surely must have been filled with songs and poems now long forgotten.