Doing a skybox presented a few frustrations, but a very rewarding result.
My general strategy for the skybox was to texture a cube (with all vertices at a -1 or 1 coordinate) that surrounded the camera, without depth testing. It would use the camera’s rotations, but ignore it’s translations.
To ignore depth testing, simply disable GL_DEPTH_TEST, render the skybox, enable GL_DEPTH_TEST, and then render the rest of your geometry.
The cube was textured with six separate images (one for each face), instead of just one. This meant I had to determine which face I was on in the shader and choose the corresponding texture. I mistakenly tried to do this in the vertex shader (for more hours than I care to admit) by testing which plane the current vertex was in. The problem with doing this in the vertex shader is that all of the vertices are in three of the six planes… This meant that only two sides of the skybox would show up, and the other four would never have been given colors, leaving them to be random values from memory.
Once I moved that logic to the fragment shader, everything was almost perfect. Two simple fixes remained. The first was that some walls were inverted, due to mapping 3D coordinates in one plane to 2D coordinates in a different plane. That simply meant inverting texture coordinates where necessary. The other issue was very visible seams at the 12 edges. This required changing the texture wrap mode to GL_CLAMP_TO_EDGE. No other wrap mode would work for me.
I recommend using textures that are at least 512×512 each. I originally used 256×256 and that quality is not very pleasing. The demo video uses 1024×1024 textures.
Here is a gallery of some relevant code: http://imgur.com/a/JyJsg#0
Here is a video demoing the awesomeness of skyboxes:
Credit to orindoomhammer for the skybox texture that I cut apart.