Stephen Fry's radio programme today was on the subject of the word 'Hallo' (listen again here for another week). I would spell the word 'hello' and there is also a third variant - 'hullo' but the BBC spelt the programme title Hallo with an a.
The first recorded instance of hallo, hello and hullo was only in the 19th century, according to the OED. Someone on the radio programme suggested that the word has its origins in hunting and dates back to soon after the Normans arrived in Britain in the 11th century. A cry similar to 'hallo' indicated that a deer had been spotted. Shakespeare uses 'halloo' and 'holla' not as greetings (those would be 'How now' or 'Well met'), but as a way to attract someone's attention. He also makes verbs of them, suggesting that they were well-known words at the time.
Another greeting used in Shakespeare's plays is 'What cheer?' Cheer is a word that can be traced back to the York mystery plays. It formerly meant 'disposition' so 'what cheer?' meant something like 'how are you feeling?' In the 1890s 'what cheer' morphed into 'wotcher' thanks to Victorian music-hall songs, a greeting that is still used today, mostly in London (a character in Harry Potter says it).
The radio programme, Fry's English Delight, is not meant to be an academic look at words, but it's an interesting listen. You can listen to the programme (it's the last in the current series) here for a few more days (I'm not sure whether it's available to listeners outside the UK).