Redstone circuits are based on two items, Redstone Dust and Redstone Torches. Both of these items are mined from Redstone Ore. When you mine Redstone Ore, it drops many pieces of Redstone Dust. To craft a Redstone Torch, you put a stick in the crafting window with one piece of redstone dust above it (like a regular torch but with Redstone instead of Coal).
When Redstone Dust is placed on a block, it becomes Redstone Wire.
Redstone Torches are power sources. When placed adjacent to Redstone Wire, the wire will become powered and begin to transmit power. Redstone Torches can also be thought as a NOT gate. If the block a Redstone Torch is placed on receives power, the torch will turn off. If the block is not receiving power, the power will stay on.
Buttons, levers, and pressure plates all transmit power as well. A button will transmit power for about 2 seconds, and then turn off. A lever will not transmit power if the lever is in the off position, and will transmit power if the lever is in the on position. A Wooden Pressure Plate will transmit power if any object is on it (dropped items and empty minecarts count), and a Stone Pressure Plate will transmit power if a mob or the player is on it.
Doors, TNT, and minecart tracks accept power. Doors are fairly straightforward - if the door receives power it will open, and if it doesn't receive power it will close. If a block of TNT receives power, it will ignite (good for making TNT-based traps). If a minecart track junction receives power, it will switch directions.
It's important to note that doors can receive power from the blocks surrounding them. If you want to make something that opens the door momentarily when you hit a button, or open when you step on a pressure plate, you don't need any Redstone Dust - you can just place the button on the block next to it / pressure plate in front of it.
However, Redstone has its quirks. Power can only travel 15 blocks across Redstone Wire. If you have a long strip of Redstone Wire 20 blocks long and place a Redstone Torch at the beginning, it will reach the 15th block and the remaining pieces of wire will be unpowered. To circumvent this issue you can build repeaters, which are simply two NOT gates in sequence (switching the signal twice results in the same signal).
Also, Redstone can burn out. If you make a circuit that is designed to flash on and off too quickly, it will eventually stop working until you remove a part of it and wire it up again. Specifically, a device that flashes on and off every 1, 2, or 3 ticks (there are 20 ticks in a second) will burn out.
Here is an image with various logic gates taken from the Minecraft Wiki - the article there has more info on each gate.
Redstone circuits are generally shown through schematics like this one:
These are three designs for an AND gate: output O is only on when inputs A and B are on.
Using a combination of these gates, you can make many things. For example, a Monostable Circuit. I picked this example because it uses an RS-NOR latch and relies on the burnout quirk.
(image from the Minecraft Wiki)
When a button is pressed, it delivers a signal for a while and turns off. This Monostable Circuit will extend the amount of time a button press delivers a signal. The navy blue section of the circuit is an RS-NOR latch. The green section is a clock that will burn out after a while. When the button is pressed, the RS-NOR latch flips and activates the clock. When the clock burns out, the RS-NOR flips back. This makes a circuit that will extend a button press.
Here's what is looks like in-game:
Now that many new Redstone items have been added, I felt it was time to revisit this answer. The first (and probably most important) item that was added was the Repeater (added in Beta 1.3)
The Redstone Repeater is a unique block, as it has 4 different settings. You can cycle through them by right-clicking. You will notice that each setting places the "Redstone Torches" farther apart. This is because at each individual setting, a Redstone signal will take longer to propagate through the item. The settings are 2 ticks, 4 ticks, 6 ticks, and 8 ticks (or 0.1, 0.2, 0.3, and 0.4 second delays).
The Repeater has also been called a diode, because it only lets a signal travel through it in one direction, much like an actual diode does. Repeaters will only accept an input directly into it.
Another interesting property of Repeaters are that they can "power" a block if the block is placed right after the Repeater.
Some uses of Repeaters are compact (adjustable) clocks:
And having isolated parallel signals:
Beta 1.5 brought Detector Rails and Powered Rails.
Detector Rails will simply give off power if a minecart is on them, and not if there is no minecart on them.
Powered Rails will act as brakes with no power applied to them, but will boost a cart if power is applied to them.