It depends on the player, really. Most of my players have hectic work schedules, so don't have plenty of time to craft an elaborate story. What I do is talk via icq with them and help to create a sketch of a story. Sometimes I myself work up the sheet.
Then there's the fact that not everyone is a Tolkien reader in my group. Most have only seen the movies (which is just fine with me), but it takes a long time for me to explain a bit of the earlier history of Middle-earth.
There was a funny moment just last week... one of the "uninitiated" players wanted to make a Dwarf character and he went on to suggest how he wanted to play an champion of some church who has been betrayed by the high-priest so he would become sort of an Avenger... I interrupted him and went: OK, that's fine, but this is really impossible to do in Middle-earth. See, there are no churches...
No matter where you go, there you are.
<div align="center"><center><table border="1" cellpadding="0" cellspacing="0" width="200" bgcolor="#FFFFFF" bordercolor="#000080"><tr><td><center><br><font face=verdana><font color="#000080"><font size="2">I am</font><br><font size=8><font face=symbol>p</font></font><br><br><font size=2>Everyone loves pi</font></font><br><font color="#FFFFFF">_</font></font></td></tr></table></center></div><br><center><font face=verdana><font size=2><a href="http://www.geocities.com/eyecanspy/numberquiz">what number are you?</a></font><font size=1><br><br>this quiz by <a href="http://www.livejournal.com/users/orsa">orsa</a></font></font></center>