1. Q the damage is great
2. E the extra jump range is awesome
3. R going invisible (and turning red) is pretty sweet
4. W Just because you can

I don't upgrade the W because it is minimal CC and hopefully others on your team are CC oriented
If your team is really that bad that you are supposed to be the primary CC by all means try upgrading W earlier.... I will not.

You have a very fast jungle, so I like having a strong leash on blue (PREFERABLY: wolves first if you have a smart enough team to help you out) and saving my smite for red.
I save my smite because if you don't I've gotten to red with 20 seconds left on CD for smite.
With that super quick jungle to red I go straight to gank.

You now have a nice "leap" to get in the battle, then a quick Q then W for damage. Use Q before W because W has longer range.

Now I know this will need explaining because it isn't the conventional 21 and 9.

Kha'Zix has an amazing burst ability, and his Q is on such a short CD that adding some CDR with the masteries and runes is fantastic.

He also does a lot of damage with this Mastery guide.

The Objection people have is that they want more defense.
You're supposed to be an ASSASSIN!
You go invisible, you have a jump, you have flash. These abilities are there so you can dive in, do damage, then stay alive. The 3 you lose on defense and add to attack is worth it.

If you're having trouble move 3 from Havoc to Vampirism.