Effectively a shader is just a set of commands that go straight to the GPU.
They are more effecient than processing the data through the engine (the way things used to be), as engine code goes through the CPU and then gets handed off to the GPU after the CPU realizes it doesn't need to do anything to it.
Now a bit more detail...
You have two types of shaders - Pixel Shaders and Vertex Shaders. Each of these come in a bunch of different versions. Not only do you have the PS 1.1, 1.4, 2.0... but they also exist in different languages. DirectX 8.1 uses assembler to write shaders. OpenGL uses the Cg predominantly. DirectX 9 uses HLSL. Cg and HLSL are a lot easier to work with (IMO) but they all effectively do the same things.
For the Pixel Shaders you are manipulating the texture of a model (or level geometry...sprite...). Now this can do a lot of things from a simple make it red or blue task - to really complex tasks like per pixel lighting with a procedural texture and normal mapping. Simpler tasks can often be done with a pixel shader alone, but most of the fun stuff requires data passed from a vertex shader.
Vertex Shaders deal with the vertex data of models. Many times it just gets the vertex position and orientation and passes that info off to a pixel shader for processing (as is the case in per pixel lighting) - but you can also use a vertex shader to deform the mesh. Some examples of this are the wavy grass shader and some water shaders. Whenever you are using a vertex shader it over rides the fixed function vertex pipeline...so if you are using a fixed function effect in conjunction with a shader you will have to take this into account (only for that model...other models in the scene are unaffected).
Now some more info...
Shaders take time. No matter what you may have heard - they are expensive to run...it is not a silver bullet by any means. The more shaders you have on screen the slower they will be. For example if you have a fur shader on a dog, a water shader on the dog's water dish, a gloss shader on the dogs collar, per pixel lighting on everything, a glow shader on the light and bump maps on everything - the scene will quite likely render piss poor slow even on a top of the line system.
Shaders can only manipulate...not create. Vertex shaders can move vertices around the screen...but they can not create anymore than what were in the model to begin with. Pixel Shaders have a bit more capability in this region...but even they do not allow you to run square up on a wall without pixelation.
