The storyline should be a guide -- if you hold to it too rigidly, the players will know, and will start to feel as if they are just being pushed along. If you allow the players to guide their own paths, it will not only be more fun for you, because you'll encounter the unexpected, but it will be more fun for the players, because they will feel like they're a part of their own destiny (which they are!)
To create a storyline, consider where the players are going next, and what their intentions are. They'll probably, as play develops, create some goals that they'll be pretty attached to. It’s important to think of what province the characters are in – the Old or New World is the recommended place to start, not only because most of the information on this site comes from an Old World perspective, but also because it serves as a diverse base from which any of the other provinces can be explored.
Let’s take a previous example and say that the players are traveling to Aranor to seek their fortune. One of them is a mage, and is seeking a teacher to learn more magic.
Use that basic formulation and then flesh things out. Who are they going to meet when they arrive? A friendly dockhand, or a thief trying to take advantage of those who are new to the city and who leads them into a bad part of town? Will the mage get some leads that might find him a teacher? Perhaps the teacher will have all the knowledge the player desires, but will be very hard to deal with on a personal level.
Or perhaps they won't make it to Aranor at all, but will encounter a storm on the way and will be shipwrecked on the desolate, unexplored northern shore of the Old World and have to find their way back to civilization, perhaps with a mess of fellow shipwreckers in tow.
As a rule, your players are going to be pretty exceptional people -- they are going to have natural attributes and skills that are above and beyond the ordinary. So naturally they are going to get more attention (because a player is beautiful, or carrying a wicked-looking sword on her back, or using magic) and attract unusual circumstances.
Get a basic storyline in your head -- check out Ideas for Adventures in the Guidelines to get your imagination started -- and then see how your players influence things.
One of your best tools will be encounters -- to find out more about them, see- Creating Encounters.