Well, for starters, characters need traits that make them human, and should have redeeming qualities along with tragic flaws. Next, all stories are about change. Third, all stories are a dialectic between opposing forces (which could be anything, from armies to values), and it's how characters respond to those opposing forces, for better or worse, that makes a story. The struggle between the opposing forces should be made apparent in the story. Also, keep in mind timing. What may be clumsy and awkward at one point may be completely appropriate at another (I'm sure the love story would have seemed goofy had the war not been the backdrop to it, and the war just gave it all the more power), so go ahead and ask yourself, "Why now?". Characters take time to build, so reuse them. It's also all right to
slightly exaggerate qualities of characters, both good and bad, making them larger than life but still convincingly human.
It takes practice. That's why I like NESing. It's perfect practice for story writing. This may seem like a tall order at first, but just try to keep it under control; don't go overboard, and don't worry too much. For me, it comes naturally. I'm not sure how great these tips are in this context, but I suppose the biggest tip for stories, the one I always keep in mind, is this: in the end, something has to change.
EDIT: Most NES stories (updates not included) fall into either vignettes, flash fiction, or short stories. These tips are probably most appropriate for the short story: the other two have different goals and requirements. Here's a link providing tips for flash fiction, which is just really short short stories:
http://www.fictionfactor.com/guests/flashfiction.html
The key here is economy. EVERYTHING should be small.
Here's a link on writing vignettes:
http://www.how-to-write-anything.com/vignette.html
Vignettes are basically slice-of-life prose. They're more meditative. They're also easier to write.
Just trying to help.