This is the bit where I make statements that people disagree with... ah well. It's all good.
A game's story is the most important part of the game. I would go so far as to say that the story is the only essential part of the game.
Now, this is where the graphics artists & gameplay people jump out of the bushes. Bear with me a bit first, then feel free. 
I will play and have played almost every game genre under the sun. The games I have enjoyed have been many and varied, depending on mood and interest. But the best games have been those with stories I have enjoyed, stories that are written well, acted well, spoken well and given to the player well.
Essentially, a computer game is (or should be), at it's core, another medium for the expression of a story. The story is what the player is playing for, to find out what happens next. Now, here people jump in and talk about gameplay and character - but those are really elements of the story as well, especially character. The story is especially important in an RPG-style environment - as the RPG is probably the most 'overt' story-telling form of game.
As RD said, "the game is the work of the story teller and the graphic artist gets the line in the credits department." I agree with this wholeheartedly - the game is the story.
Now, writing a story. Writing is about 10% creativity, and about 90% perseverance - especially when you're writing longer works, such as novellas or novels - or indeed, a game script/story, or for that matter a screenplay. First you need the idea - and ideas can come from anywhere, and can be about anything. It doesn't matter where your inspiration comes from - it's where you run with it that matters. That's the creativity part - making a story that is original and interesting, and getting it going, with clear ideas of where it's going to finish - like a skeleton of the final beast.
Now for the perseverance. The hardest part of any story is getting it right. I recently did a writing course at Uni (in fact, I'm changing my major shortly, if all goes well) and as part of that course I had to write a pair of portfolios - one prose fiction, the other a composite script/poetry. The prose fiction piece I wrote was around about a thousand words long - 1073, if I remember correctly. Now, that's only a couple of typed pages, which might not seem like a lot of work to write. In my files, however, I have a stack of pages around sixty thick, comprised of drafts of that story. Each one is scribbled on liberally with red and green pens, in different places, in similar places. I have another fifty odd copies of my original version (which is very different to the final) with workshop feedback from the class. For my script, which was ten pages long, I have over a hundred different printed sheets that have been revised, scrapped, reused, edited and scrapped again. Poetry much the same.
My point? The hardest part of writing a decent story is getting it right - editing it down to the point where you are satisfied. Myself, I'm not satisfied with my work - I'm planning a return to it, especially the script, based on the lecturers feedback and my own revisions. My lecturer herself wrote a novel as a thesis project when she was getting her Ph.D. Seventy five thousand words or so - and she's been trying to get it published for several years now, and has redrafted it (read: rewritten it) no less than nine times. A bit perfectionist? Perhaps - but that's often what it takes to get your story perfect. A dash of creativity, followed by a lot of stubborn perseverance.
What can you do when you're writing down ideas? Well, the most important thing is this - don't ever fall in love with your own work. If you go back and read something and think, 'It doesn't really fit here, but I kinda like it...' then you're going about writing the wrong way. Be fully prepared to rip up whole pages of work - it's better in the long run if you aim for perfection. No matter how much you like a phrase, be brutal with the dead wood.
Other things, almost as important? Feedback, feedback, feedback. Give out a hundred copies to anyone who'll read it for you and comment. Act on their suggestions - especially if they write themselves. Ask them if things work, and if they feel something doesn't work, ask them why. When writing dialogue, get a few friends together and have them read it aloud. See if it sounds like real people talking. If it doesn't, make it sound real. Then edit, edit, edit, and ask for feedback again.
Eventually, of course, you'll run against the wall of "that's enough" or the point where you think it's about right. Then give out a couple of copies to people whose opinion you really trust, and ask them for any small touches they'd add. Put them in if you think they fit... and now, go back, reread your first drafts (Oh yes, keep a copy of everything! ) and see how much better your final feels... hopefully a whole lot. Give yourself a pat on the back... and then?
Write some more.
And, if you really don't feel like writing yourself, and you're looking for a good place to start, you could always drop by places like, say, the (url="http://"http://www.ambrosiasw.com/cgi-bin/ubb/forumdisplay.cgi?action=topics&number;=49")Coldstone Chronicles(/url) and see if there's any writers there you think you'd like to work with. Hunt around a bit - never know what might turn up.
Hmm. That was long. Ah well. I'm a writer, what do you expect? 
-Andiyar
------------------
"Any good that I may do here, let me do now, for I may not pass this way again"
