What's the most elegant way to apply fog to a skybox?

My game allows players to dynamically adjust the "visibility" of the scene they are playing in, which controls the fog density and camera far clip distance.

With lots of fog, it looks ludicrous to see a perfectly clear skybox above a single color skyline.

What is the most elegant way to begin "fogging" the skybox once the scene visibility drops below a defined threshold? It needs to be non-destructive to the original skybox images, as players can increase the scene visibility just as easily as decreasing it.

I think you're looking for an answer about programming a better skybox, but I think a better way to approach your problem (the skybox and fog look weird together) is to begin "artistically".

Your skybox and fog look unnatural to you because they don't go together. Take a look at some pictures of aerial perspective and Rayleigh scattering. Distant mountains appear purplish at night and bluish during the day, not because of blue fog, but mostly because of scattered light and some color contribution from particulates in the air.

A quick fix is to begin tweaking the values of your ambience, directional lighting, fog color, and skybox to "go together", so they all represent the same conceptual time, place, and weather.

In real life, if your scene is actually foggy or smoggy, then you shouldn't be able to see the sky at all, and if this is what you are aiming for, then remove the skybox all together and set your clear color (background color) and fog color to the same value.

This might help:

http://www.chadchatterton.com/posts/2010/4/17/the-sky-above-the-port-was-the-color-of-television-tuned-to.html

You can use Unity’s default GlobalFog.cs (Included in Standard Assets), it adds a good effect to the height of scene which covers a skybox.
But this can be a heavy task if your target platform is mobile.