What is it about lullabies that sooth a child to sleep?
What characteristics in music should I look for when trying to find new lullabies to sing to my newborn?
For mine, it wasn't the song, it was that I was the singer. I chose from my favorites, so my kids got lots of Ella Fitzgerald and Billie Holiday, but honestly, I could have sung Black Sabbath and they could've cared less, so long as it was sung in a quiet, soothing fashion.
If you need some specifics, there were several threads at the HiveMind that I perused while looking for new things to sing to my kids at naps and bedtimes.
Pete Seeger says "a lullaby is a work song, and should be sung by the luller." A work song is a folk song whose rhythm helps people do a job, whether that's a bunch of people pulling up an anchor, or one person putting a baby to sleep. So the most important aspect of a lullaby is that you be willing to sing it. Abiyoyo is a great record with some lovely lullabies on it, but I can't sing them because I'm not that good. (In contrast, any child who asked Where Are My Pajamas? would find themselves in a song right quick.) We also had a Woody Guthrie album of children's songs that I can't find online that my kids loved to listen to as a way of exhausting themselves before bed, so they acted as lullabies.
I enjoyed a record of mostly lullabies called Lullaby Berceuse, and sang many of those songs (by request) for years to my children. I also sang them Hobo's Lullaby, which I learned from an Arlo Guthrie record (I skipped the police verse) and Under African Skies from a Paul Simon record. Insipid "go to sleep" songs will make you mental. Songs with lines like "things go right, things go wrong, ... you will grow up big and strong" are less annoying to repeat a lot.
Find songs you like, especially if they're a little slow. You can always slow them down, I sing Hobo's Lullaby much slower than Arlo does. Enjoy singing them. If you're holding the baby, let the rhythm of the song guide your walking or rocking too. If you have a recording of the song, start by playing it, then singing along, then singing it alone. Later you may be able to just play it for the baby who will associate it with your singing. But you may find that an appreciative audience keeps you singing (happily) for a long time to come.
For newborns, I agree with the other answers - you singing is what's important.
For toddlers, one important thing to keep in mind for 'sleep music' is that you should choose music with no words. Music with words will keep their brain engaged more than music without, and will not help them fall asleep as quickly. I typically sing whatever song my two year old asks for for about 10 minutes, and then after that it's wordless tunes until he falls asleep.
In my experience the content is irrelevant. The best lullaby is the parent's voice singing anything in a soft, melodic fashion. If you need a starting point then you can't go wrong with twinkle twinkle little star. After singing it 200 times it can get boring (for you) so keeping the same tune and replace the words with anything which comes to mind. Perhaps a shopping list of what you need from the supermarket. Really, all that matters is the tone.
If you're looking for something to leave them with whilst you leave the room then perhaps record yourself singing something?