Like all other noble houses, Stark must look for a good combination of Barrels, Crowns and Fortresses/Strongholds. Unlike most other Houses, it can do so mainly unthreatened...at least for a couple of turns. Also, unlike most other Houses, Stark needs to expand southward in order to quickly secure and fortify Moat Cailin. Expansion in any other direction, other than to secure icons you can't find elsewhere, is a thinning of forces and will come back to haunt you.
Don't make the mistake of leaving your home province undefended. Sure, with the garrison troops from the expansions (and the 2nd edition core game) it'll be not nearly as easy to take; however, leaving your backdoor open will take away Stark's number one advantage: having only one front to fight on...the south! So make sure you keep enough troops around while expanding southward and build a ship or two when mustering comes around.
Also, don't make too many enemies too early on. Make friends. More importantly, make friends on the nothern part of the continent. Why? I have observed that friends in the south will largely do as they please. And sooner or later they will realize that there is only so much you can do to help them in their fight in the south and there is next to nothing they can gain in the north. At which point they usually decide to switch sides and ally with another neighbor they have more in common with.
About halfway through the game is usually when House Stark reaches its peak. It has expanded as far as it can without thinning troops too much, and at the same time it has usually two neighbors. In a 6 player game, that means half of the game goes on without Stark having any influence -- which means alliances are forged without Stark having much to say.
You need to position yourself so that only few players see you as a threat, and a mediocre one at that. Have a spearhead (or be ready to form one within one round) that allows you to take part in conflicts elsewhere on the continent. Otherwise you will be isolated -- both from allies and from the constant back and forth that is necessary to take advantage of to win the game.
House Stark has one big advantage: its secluded territory in the north. Only Greyjoy could bump into Stark very early on, and they can usually be reasoned with. As long as you have a substancial fleet in place to protect you western shore, you should be fine. Same in the east, however; protect your shores!
Near the end of the game is when Stark is usually the one having a hard time pushing into other people's territory. Sure, that counts for every player. But it is the map that makes the difference here. If you didn't think ahead enough, you can pack up and watch the game from the side line.
What I usually see happening is this:
In the early stages of the game the other players are at each others' throats and way too busy dealing with Stark. Once the borders have been set, however, their eyes start peering northward...especially if Stark has been largely left alone and spent the time to expand further than the other houses would have liked. If you're not careful enough, suddenly you have Baratheon and Greyjoy pounce on you, possibly with some help from House Lannister. And you won't have an ally that can effectively help you...plus your ally has nothing to gain from helping you.
If you managed to stay under the radar so far and Houses Greyjoy, Baratheon and Lannister have all peered nothward only to avert their eyes to more immediate troubles concerning their neighbors, strike and alliance with one or two of them. Make sure you don't advance to much.