Vel'koz is an incredibly powerful champion that has the ability to turn entire fights either putting your team further ahead or bring your team back from a deficit with his hard hitting passive which applies true damage. Team fights are where Vel'koz shines, hitting entire enemy teams and melting through even the tankiest targets if his position is right.

Pros

Massive source of true damage

Low mana costs

High base movement speed for a mage(340)

Long range

Massive Laser of death that makes things dead

EWQR combo pretty much kills anyone

Very spammy champion, from the enemy P.O.V. it feels like a never ending onslaught of stuff to dodge.

Amazing and instant autoattack.(bypasses Yasuo's wall!)

Cons

No mobility and unreliable defense makes him a prime target for assassination and focusing.

Relatively low ratios(~0.6 for all abilities)

Ultimate can be interrupted, it must be cast from a safe place.

4 skillshot kit, everything can miss.

His W is completely reliant on CC for it to deal its full damage.

Odd mechanics, his Q/W/R all have unique mechanics that some might find difficult to get used to.

Massive model, as big as Gragas but no where near as tanky.

Greater Seal of Armor is a strong option, even since nerfs. Vel'koz is already extremely fragile, and these allow you to take a few more hits while in lane, increasing survivability. Also helps a lot against AD mid champions such as Zed or Yasuo. These have more of an impact than the mana regen seals in the late game.

Greater Seal of Scaling Mana Regeneration is the seal that I personally prefer. Between these runes and a Chalice of Harmony, I don't usually have any mana troubles at all. Vel'koz is already slightly mana starved, so I feel these have a decent impact and help you in the early levels of the game. The one problem I have with these is that I don't feel they do anything late game.

Greater Seal of Scaling Health seals have become a lot more popular since armor seals have become weaker. gives +216 hitpoints at level 18, which is a fair bit more health than a free Ruby Crystal. This can come in handy on Vel'koz because of how fragile he is. Though I feel like armor seals would be ideal, these runes would be more effective against mixed damage.

Greater Seal of Magic Resist is a possible choice if you don't feel comfortable starting without MR. However I don't recommend it as much, because getting an early Chalice of Harmony gives a good amount of MR already.

Glyphs

Greater Glyph of Scaling Ability Power is what I recommend because Vel'koz is a champ that is based off of Ability Power. While the flat AP glyphs might seem better at first glance, these scaling ability power runes start to outclass the others at level 7.

Greater Glyph of Ability Power is something that wouldn't recommend. As I said, while it may give you more ability power initially, the scaling ability power runes become stronger at level 7. These runes would be acceptable if you want to gamble for an early lead and try to snowball.

Greater Glyph of Magic Resist is a possible choice if you don't feel comfortable without starting with MR. However I don't recommend it as much, because getting an early Chalice of Harmony gives a good amount of MR already.
Quintessences

Greater Quintessence of Ability Power is what I prefer and highly recommend. These 3 runes alone give you a whopping +15 extra AP, equivalent to a Doran's Ring. This gives your early game damage a huge boost.

Greater Quintessence of Movement Speed is a viable option. All together they bring about +4.5% more movement speed to the table. Mobility being one of Vel'koz's biggest weaknesses, these runes can really help compensate.

Greater Quintessence of Magic Penetration is yet another viable choice, since Vel'koz has high base damage on his abilities. I personally feel that while these are a viable choice, stacking ability power is more efficient, especially at early levels.

I choose to go a more defensive route of summoners on Vel'Koz. I do this because he is very long range and vulnerable early-game. Both of these cause me to think that taking heal on him over Ignite is the smarter choice because it will make him much harder to kill in lane, therefore he shouldn't really get behind, enabling him to have a better chance of getting into mid to late game well off. Him being long range doesn't really let him get ignite onto the target he'd like to be bursting most of the time as well so it isn't really a very strong choice on him. Ignite would make his killing potential higher in lane but he isn't a champion who needs to snowball to be effective and it just makes him so vulnerable that it isn't worth the trade-off in my opinion.

I've gone over laning a decent amount throughout this guide but I'll summarize it all here again. Overall, Vel'koz's laning is safe and you have a lot of room to harass and feel the lane out. You do need to make sure you are staying up on your warding at all times as you are very vulnerable to jungle ganks overall. With the kind of junglers that are popular right now you can easily get punished for being aggressive at the wrong time so /please/ make sure to always be safely warded at all times while being aggressive. If you don't have any wards up and you don't see where the jungler is then it is best to stay back and just farm the lane out until you do.

Overall, you'll be spamming Void Rift all the time to clear out the wave and shove it. Hitting your lane opponent is an added bonus and you can maybe chain it to pop a passive proc on him in conjunction with Plasma Fission and some auto-attacks if needed to extend the time available to you. Be /very/ careful about using Tectonic Disruption aggressively. If you use this ability and you get ganked, you should die. Only use it aggressively when it is safe to.

You're pretty terrible at roaming since you are slow and if you get caught inbetween lanes you're gonna die. Stick to your lane, farm jungle if you're unable to be aggressive and in lane and just overall default to farming if you're not sure what to do. You can always follow your lane (if you deem it safe to!) to countergank as you are fantastic at these due to your long range and good amount of cc.

Mid-Game

Going into mid-game, you should have your Sorcerer's Shoes - Alacrity completed as well as your Athene's Unholy Grail. You excel at team-fighting and sieging so that is what your team should be doing; forcing things as a team. When you are, make sure that you are positioning yourself very carefully. If you put yourself in a position to get cc'ed you can just pop like the little eyeball you are and cost your team the fight and even the game. Stay on the edges, harass with Void Rift and Plasma Fission and mostly save your Tectonic Disruption to either peel for you or your adc or follow-up with another cc.

For fights, you should be dancing around the edges spamming Void Rift and Plasma Fissure while, once again, waiting for the right time to use your Life Form Disintegration Ray and Tectonic Disruption. Using them too early can result in you and your teammate's death as well as a lack of optimization of your damage. Remember that your laser goes through everything and has almost a billion range. Use it when the right time presents itself. No sooner. No later.

There are a few champions that vel'koz works very well with.
Jarvan IV- cataclysm makes ulting a whole team very easy, in addition you can knock up their whole team while they're stuck in it with him.
Sona- Mass stun due to cresendo. depending on their position, a good Vel and Sona could win a team fight by themselves
Amumu- same sort of reason as the other two, it removes the enemy teams ability to escape from the ultimate.

Alright, thats about it for my first guide. i hope what you picked up from this was that vel is a skill-shot only, long ranged caster, who has very high damage output if you can combo his abilities right. in addition, i gave some examples as to who works well with him, which should help if you're duo queuing or in a team.
Now, go, and explore.
You'll learn so many new things, but your enemies will only learn the meaning of pain.