Most video games benefit from having a sky to increase a feeling of immersion and most of those skies are in the form of a box, a skybox. The way the sky looks can greatly alter the feeling of a game from bright and happy to cold and gloomy. Just picture Katamari Damacy with overcast or Dear Esther during golden hour – it would change the feeling of the entire game.
The skybox is essentially anything beyond the immediate environment that the player will see: it can include the horizon, the sky, and even the ground.
Over at GamesRadar they have a very subjective take on what they consider to be the best skyboxes in video games. I just like the fact that skyboxes are being evaluated in this way.
The design of the skybox can literally change the atmosphere of the game. It can quickly establish if the player is on a different planet like in Mass Effect or if magic is twirling in the air.
Most skyboxes are done in 2D, and can be made realitevly easily in your image editing software of choice. Unity3D has a good writeup on how to create a skybox and use it in their engine. It is possible to make 3D skyboxes and Valve has implemented such a feature in their engine, on their developer wiki you can see how they work and how to make a 3D skybox.