Sejuani doesn't have the ability to focus hard and do a lot of damage to one champion, however her aoe damage can be extremely high even with a tanky build and her Crowd Control is unmatched. If you play Sejuani right, you should have a few kills, very few deaths, and an outrageous number of assists. Sejuani is usually not effective 1v1.

I started this guide the day Sejuani came out. It's far from perfect, but I just want to throw out my ideas and then over time make it better with help from your comments and criticism. Please test it out and let me know how it could improve. Please don't downvote until you've read my explanations or at least tried the build out yourself. Please leave feedback so I can make this guide the best out there! Thanks!

Pros

Rides a pig (This would be enough to convince most, but there's more)
Unmatched CC
Tanky Mid-Late Game
Lots of Damage

Cons

A bit squishy early game
Mana problems early game (unless you have blue. Typically no problems after you get sheen)
Her skins are not that cool...
Lacks any ranged attacks except for her ultimate.

Passive:
Soooo Great. Permaslow passive! It's like having frozen mallet but without paying for it. This makes people SO MAD.

Q:
This is what you use to engage enemies, to close distances, to escape, and to apply your passive. I get this skill second but max it last. Maxing this isn't going to improve your ability to engage, to escape, or to apply your passive, and the damage doesn't scale as well as with your other abilities, so put 1 point in it, and then don't put any others in it until you have to. Remember that you can use this to go over walls if you're chasing someone or running away. Although use sparingly because the cooldown is roughly 15-19 seconds.

W:
This skill is awesome. It doesn't apply your passive but it scales with AP and with Health. If you follow the recommended build you'll have around 4-4.25K health by the time you get to full build. You get this ability first because it lasts a long time and is going to be your main damage source in the jungle as well as in laning. I generally max this skill first. Once you get to full build this spell is going to be doing 150-200 damage per second to EVERYONE around you. This is amaaazing in team fights not only because of the damage it does, but because of the low cooldown and the length of time it lasts. You can have this ability on almost constantly. Note that this does more damage if your passive OR permafrost is active on the target.

E:
I get this spell at level 4 and max it second. How do you use this spell? When in the jungle or fighting minions, obviously the slow is useless and you want the damage it outputs (quite high damage). The problem with this spell is that it doesn't put out any damage or slows (it does nothing) until your passive is applied. What you do is you charge in using your q which will apply your passive to everyone you hit, then you immediately use your E to inflict high damage on everyone you hit.
When fighting players do not use this spell until 1: obviously you need to make sure your passive is active on them or it will do nothing to them but probably some minion you hit 2: It has a long enough cooldown that in the average PVP fight you're not going to get to use it more than once, so when verse 1 or 2 enemy champions you DO NOT use this spell until they begin running away from you or you begin running away from them. This will apply the insane slow and allow you or teammates to chase them down and finish them off or it will allow you or your teammates to get away if you're on the bad end of the battle. If you use this immediately after engaging it will do damage, but chances are the fight will continue until after the permafrost wears off and you won't be able to use it to chase them down or get away, unless the fight is really long.
Note that your passive only lasts 3 seconds so use E before as soon as possible after you stop hitting the enemy to apply the damage and the slow.

Ultimate:
Pretty self explanatory. Stuns enemy champions. Note that the first champion hit will be stunned longer and surrounding enemies will be stunned for a shorter period of time. Most effective when used against groups of enemies but also very useful for chasing down a single kill. The cooldown is pretty long on this, so only use it if you need it to get that kill or to escape someone chasing you.

Obviously smite is absolutely necessary if you're jungling. Flash or ghost should be your second. Flash or ghost are highly recommended although may be unnecessary because of your insane cc and your Q. It depends on what type of team you're against. If you don't find flash or ghost useful I would use teleport, or cleanse (for vsing teams with a lot of CC). Exhaust is also a good choice. Only get ignite if the team you're against has a lot of healing and no one else on your team has ignite. Really avoid ignite if you can, someone else on the team should get it.

For better explanation of my skill sequence see "Explanation of Skills"
In a nutshell:

Max W first because it does high aoe damage for jungling, killing creeps, and team fights. Your lowest CD, scales well with AP and Health.

You max E second because it has much better damage than your Q and the slow is extremely OP.

Get Q at level 2 but max it last. Like I said in the Explanation of skills, you use this to chase down, to get away, to close distances, and to apply your passive, but the damage isn't as good as your other spells and the CD is longer, so you really only need one point in it for it to be effective.

R: Obviously put point into your Ult whenever possible. This takes priority over all other skills.

I had a hard time with the masteries. I wasn't sure whether I should go 21/0/9 or 0/21/9.

0/21/9 works well because it helps early game with jungling, and the extra health you get from defensive masteries scales with your W ability, which also helps with jungling.

Eventually I decided to go with 21/0/9 because Defensive masteries do help a lot late game, but late game you're already extremely tanky, so they're often unnecessary. I like the extra damage.

Typically I would recommend 21/0/9 but there are special circumstances in which I would switch to 0/21/9. If the team you're against are using a lot of champs that are strong early game, the defensive masteries might help a lot in early ganks.

Why Trinity Force?
I don't see any other builds using trinity force and it's not in riot's recommended build (but when is the recommended build actually what's best?). It dominates on Sejuani. Every single stat it gives helps immensely. It's a perfect item for her. The mana in sheen really helps with mana issues too.

Why not froze mallet?
With your passive, permafrost, trinity force's move speed increase and slow, and red buff, you really don't need froze mallet. Although, if you don't go with trinity force, I'd definitely get frozen mallet.

Why not shurelyas?
Shurelya's is a good choice for sejuani, however, if you're in a ranked game you probably already have a support that's getting shurelya's, and you're already getting randuin's. If for some reason you don't have a support or the support isn't getting shurelya's, then this is a very good item choice, I would

If you do get to full build (6 full items) I would sell wriggle's lantern and get one of the other items in the build. Banshee's if you're having trouble with the enemies AP champions, or atmas if you need the damage/armor. I would not get atma's if you don't have warmogs. Since Sej doesn't have huge damage it's not worth it unless you have at least 3.2-3.5k health. If you're already plenty tanky and not getting focused I'd try the Gunblade, but I haven't tested this very much yet, so that's why I put it as last option. Let me know how it works out.

I really like warmogs because it takes you from "tanky" to "Wow he's hard to kill." Also the extra health is going to increase the damage of your w by quite a bit. (roughly 25 damage per second aoe from just one item)

I honestly haven't put much thought into runes. Some suggestions here would be great. I just used armor pen, attack speed (to apply passive) and health (for tankiness plus more damage to your w). I'm thinking of changing out the health per level runes for flat health for a better early game. Let me know what you guys think. This is the area where I need the most suggestions.

Buy Cloth armor and 4 pots. Start at blue and get a leash obviously. Smite blue. Pop a health pot either while fighting blue or right after as your health will be pretty low. Move to wolves, wraiths, then small golems, health pots as needed. Smite one of the golems then go B and buy. Usually by the time I get done with small golems my health is pretty low and i've used 3 health pots, leaving one for when you go back and do red. Go do wraiths again and then when smite is almost back up get red. I don't make suggestions about when to gank because it's too situational. It just depends on how much health you have, how much health the target has, and how overextended they are. Sometimes I gank right after blue, usually I don't. Your ganks will be much more effective once you hit 6. But still effective before 6.

This guide is far from perfect as Sejuani just came out yesterday! But please leave comments, I'd love some help. Thanks for reading!