New champ new chance to play in new interesting ways.
I will apologize for all my spelling mistakes up front.

Also note that this is the way I play Sejuani and that I play her in lane. My elo is 1515 and not 1900+ so there are definitly people who know their stuff better then me, this guide will not magically win all games for you.

*EDIT 20-01-2012*: Jungle guide added.
*EDIT 23-01-2012*: Added some more explaining in the items department.

Pro:
-She has a freaking boar! Just look at that ****!
-Best CC champion in the game
-Easy AOE farming
-Team stun
-Can do jungle

Cons:
-Long cooldown early game
-Team dependant. You can lock up the whole enemy team but you need your team as damage

Greater Mark of Armor: I chose these runes because a lot of armor helps in every state of the game. Because Sejuani should always be up close with the enemy ad carrys armor is the way to go if you ask me.
Greater Seal of Armor: See my statement about the marks above.
Greater Glyph of Magic Resist: Pretty much the same reason as why you would build armor. You don't want AP carrys ruining your day endgame and you don't want them harassing you eearly game. This should help you deal with it a bit better.
Greater Quintessence of Health: 78HP extra on a tank that will charge into the enemy team from level 1 is a big plus. This extra HP should just be enough to make you look and be really scary in the early levels.

I also tried:
Greater Mark of Attack Damage: This is usefull for the jungle because it helps you kill the jungle creeps a bit faster and thus your jungle easier but because my build isn't ment for damage dealing it will lose pretty much all it's usefullness in end/mid game.
Greater Quintessence of Attack Damage: Same as above.

Lane masteries:
I decided to try and maximize her defense against champions and the extra movement speed from utility is also really handy, it helps you chase down summoners who didn't take it all trough the game.

Jungle masteries:
Still trying to maximize her defense against champions but shifted some points around to make her better in jungle. After examinating I think the jungle setup might become her standard setup but that will need some more testing.

For summoner spells:
Flash: I still think this is probably the best summoner spell there is. The distance isn't much but with this you can flash trough 2 walls with Sejuani practically ensuring your escape.
Ignite: It's great for finishing of that last champion that ran away from a teamfight. I shuts down every champ that build himself on life steal and it's great early game damage. I practically can't play without ignite.

You could also go for:
Ghost: If you don't have flash have a grudge against it or something you should surely pick up ghost. This helps you chase those pesky enemies that just barely escaped your frost. Activate ghost hit them once with you frozen mallet and they are finished.
Exhaust: This is really helpfull to prevent that early game getaway when you can't damage fast enough yet or it shuts down that AD carry that came into the fight after you already popped all your other shutdown abilities.

For Jungle:
Smite: Because you want to kill the big mobs fast :)

Regrowth Pendant: With this and combined with your runes you should be able to take a lot of harrasement and not feel anything from it. Let them burn their mana.
Philosopher's Stone: In addition to only giving you health regen this also makes sure you don´t run out of mana. The gold gen it provides is also a big plus if you can´t get any minions.
Heart of Gold: You need more health because you want to stay up close with the enemy champions and it will give you more gold. Great tank item.
Ninja Tabi: Take this when you see/feel that the enemy team is really strong on AD. Combine this with your runes and you pretty much shut down all auto attack AD carrys.
Mercury's Treads: Take this when there is a lot of CC in the enemy team or when you see/feel their AP carry is doing his/her job properly.
Glacial Shroud: This thing gives you a lot of things you want. 1. It gives you more mana so you will never run out. 2. It gives more armor rever to the runes section why armor is usefull. 3. Your cooldowns are just a bit to long. This will help to reduce that.
Frozen Mallet: With this your health goes up quite a bit and this makes sure that at least one champion never gets away.

NOTE: People seem to think that this is out of place but let me explain a little more.
If you fail you initial dash with Arctic Assault and hit only 1 enemy and then hit Permafrost to make sure you get at least one, you will let 4 enemies escape because it takes 6 seconds for the next Permafrost. without this you will slow the enemy for 10% with your passive. Most of the time this will not be enough and all the enemies you missed will escape. With this you can just catch up to another champion and make sure he doesn't get away. It's true that Warmog's Armor provides more health but I think that locking up an enemy team and making sure you get all of them is much more important.

Negatron Cloak: You might wanna get this before completing Frozen Heart because their AP carrys is dealing to much damage. if thats not the case i reccoment skipping this.
Frozen Heart: This just makes you better on every front again and as a plus you also f*ck up their AD carrys more.
Force of Nature: The speed helps you chase even better and the health regen makes sure you stay right where you need to be. (The front line)
Shurelya's Battlesong: Again more health more mana more speed more cooldown reduction. Everything you need to seal the deal.
Randuin's Omen: With this you will shut down everything that is build on attack speed and you basically will not die from AD anymore. Instead of building this you could aslo go for a Warmog's Armor instead so will have even more health.

Also note that by the time you finished all these items you'll have a cooldown reduction of 40% and thus you can spam your Permafrost every 6.6 seconds!

You start with Arctic Assault to be able to run into the enemy team for the first blood with your friend or to run away from their first blood attempt if you get pushed around to much.
After that you should try to max Permafrost first because fo 2 things. 1. The damage is unexpected early game and 2. if you level this fast you can make sure that every chase or gank will be sucessfull as long as you hit this at the right time.
The right time would be after the used their getaway skill.
Northern Winds Does come as the second option because it will deal quite a bit of damage.

If you can and don't take to much damage you should try to harass you enemies early game.
You go in with Arctic Assault and the hit Permafrost and Northern Winds. Follow them for about 2 seconds and then run away again. if you can pull this on squishy enemy you will greatly reduce their HP and force them recall.

Teamfights:
Some people believe it's better to save it for running away but I think you should head in with Arctic Assault. If you are lucky and the enemy team was clustered enough you have just frosted all of them at once. Now just hit your Permafrost and Northern Winds to completly disrupt all their positioning and let your team pick up the kills.

Farming:
Same as killing groups of mobs in the jungle.
Charge in with Arctic Assault so you frost all the mobs and then use Northern Winds to hit them all for bonus damage, if needed hit Permafrost and watch them fall.

I still think Sejuani is best in lane but if your team needs a jungle you can certainly play it with Sejuani. My jungle build is exacly the same as my normal build only the skill sequence is a bit different.

You start at blue and ask for a good pull. Then you drink the only health pot you have and go on to wolves. From wolves to the wraiths after wraiths golem. Depending on how good the pull at blue was you will need to smite one of the golems. Now recall and get upgrade to Philosopher's Stone. Get red and start ganking.

*NOTE*: If you see a great ganking oppertunity go gank and don't waste time in your jungle following the route. Even without permafrost, every bit of damage you do to the enemy team will be appreciated by the people in that lane.

To kill the jungle mobs charge in with Arctic Assault so you frost all the mobs and then use Northern Winds to hit them all for bonus damage. After that hit Permafrost as quick as you can. Just focus on the big mobs with auto attacks, except when for the golems there you kill the little one first.

Jungle in summary:
Blue -> (Gank) -> Wolves -> Wraiths -> (Gank) -> Golems -> Recall ->(Gank) -> Red -> GANK!

At couple of things to remember:

1. Arctic Assault can go over walls. Use this to escape or initiate.
2. You are a big bully tank. YOU should initiate. Get your team together. Decide the order in which you focus enemy champions and then run in with your Arctic Assault.
3. Check if you actually frosted the enemy your charged with Arctic Assault. If you hit Permafrost right after you charge and you fail your slow you have wasted a really good kill oppertunity.
4. Glacial Prison can be used to interrupt channeling ultimates like the onces from Malzahar and Katarina.
5. I found out that Glacial Prison goes straight through a Master Yi using his Alpha Strike.
6. Don't be an ******* to your team. If they are failing don't just rage at them. Tell them what they should do better otherwise you are at just as much fault.

This is my vision of how Sejuani should be played. She requires some practice to perfect the art of charging into the enemy at the right time but if you initiate with this build i'm sure you're gonna ruin the other teams day. HAVE FUN!