A great movepool that makes him beyond excellent in UU. There's very few surefire counters for Nidoking, especially in the UU environment. He can always surprise you and kill one of the key elements of your team. However, he can be rather hard to bring in due to his common weaknesses to Surf, Ice Beam, Psychic, and Earthquake, and will always have a problem taking down sturdy Water-types.
The best UU set for Nidoking. One of the greatest threats to Nidoking is Gligar, and Ice Beam takes care of him. Shadow Ball takes care of Misdreavus, Megahorn beats Grass and Psychic Pokémon, and Earthquake gets STAB. The absence of Thunderbolt allows for a better EV distribution; Water Pokémon for the most part will take more damage from STAB Earthquake than non-STAB Thunderbolt. Give this one max Speed—it's essential for taking on Gligar that want to switch in on your Earthquake.
Choice Banded Nidoking is one of the most dangerous Pokémon in the UU environment. As with a lot of Choice Banders, depending on your and your opponent's prediction skills you could be totally messing something up or doing nothing to them at all. Earthquake should take care of Quagsire and other Water friends in 2 or 3 hits, Megahorn kills Solrock and Lunatone and puts quite a big hurting into Meganium, and Rock Slide is for Fliers like Fearow and Scyther. Sludge Bomb may seem handy for STAB, and Ice Beam catches Gligar.
Nidoking can use Counter on Choice Banders like Fearow, on walls like Solrock or even on Grounds like Quagsire and Sandslash. It does work nicely, but Nidoking is usually better off at attacking straight up. Toxic and Thief can help in wearing down opponents, but once again Nidoking is better off ramming things instead of stalling them out.
Thunder does more damage to Waters than Thunderbolt if it hits and it has a high Paralysis chance, but in the long run Thunderbolt's accuracy is better. Roar can help you against UU Baton Passers, but those are rare. Hidden Power Grass is fun on Nidoking to hit SwQuagsire for a surprise.
Rest and Sleep Talk are always a nice option on Pokémon that can take a hit or two. Nidoking can absorb a Sleep from a Grass-type nicely and then surprise them with Sludge Bomb, but it does hurt his great versatility. Protect is nice to scout for Earthquakes, Explosions, and Choice Banded moves, and helps for Leftovers recovery.
If you're using Counter on Nidoking, more defensive EVs are suggested. With 88 HP and 28 Defense EVs, you can survive a Gligar Earthquake (as long as he doesn't have an Adamant nature). Nidoking needs 200 Special Attack (the stat, not the amount of EVs) to OHKO Gligar. If you're using a -Special Attack nature (Adamant, for example), you need 68 EVs to reach that. However, without that, Nidoking already has 206 Special Attack, so there's no need to stack it any more. Generally you'll want to focus on Attack to put a little strength behind his Earthquakes, while his Special moves should be designed to kill specific threats like Gligar.
Checks and Counters
Your options are limited. Quagsire, Whiscash, Politoed, Poliwrath, Walrein, and Blastoise work as counters in the same way as the Waters from standard: they do not like Choice Band Earthquakes, and Quagsire and Whiscash do not like Hidden Power Grass, but they take the hits from any of his other moves rather well. Poliwrath, Whiscash, and Quagsire may be better off using Earthquake instead of Surf or Hydro Pump to counter Nidoking.
Solrock and Lunatone should beware of Megahorn or Shadow Ball, and Grounds like Sandslash and Gligar cannot take Ice Beam, but if these moves are not present they are great counters.