Redstone is a digital signal simulated globally when active. As jameshart said, the simulation is similar to a cellular autonoma, but there are some differences.

When it was first introduced, any signal sources would travel 15 blocks down "redstone dust" wires. Later on, this as changed lose energy each block. This was called "analog", but is really a signal with discrete (0-15) digital levels. Most sensors still respond to a signal strength >= 1 as "on", to be backwards compatible with the previous style.

This is all simulated on every 2nd tick of the main Minecraft world simulation that runs at 20Hz. This means all redstone events are computed at 10Hz. (with some exceptions in modern redstone that allows for some "single tick" events to happen. Forcing these updates that happen in the ticks that normally do NOT simulate redstone is the source of many bugs...)

Large devices are hard to build because the limited signal length required you repeat the signal 16th block. This effectively imposed a speed-of-light restriction where c = 160 blocks/s (16 block signal length * 10Hz).

The really fun part are the "active" components that made it into the game. These were very good choices by Mojang:

"redstone torch" - This is a NAND gate. the torch emits a signal if-and-only-if the block it is attached to has a signal level 0 on all sides. This obviously lead to the creation of various latches and flip-flops, and was sufficient to build the first ALUs (8-bit, supported ops: ADD, AND, [1]) and CPUs (with 8 bytes RAM and a program loader and LED front panel).

"redstone repeater" - A diode with a configurable 1-4 tick propagation delay. This was initially created to replace the NAND-inverter based repeaters that were previously required for long wires. Also, these would let you repeat a signal in one clock delay instead of two (double NAND), and took up less space making the entire build smaller (=faster). The variable timing is useful to create specifically-timed delays.

"redstone repeater w/ shutoff"[3] - About a year later, the "diode" repeater gained another input that turns it into a D-latch. (a >1 signal input to the side locks the current state of the repeater. 1-bit memories suddenly became a lot smaller and could be created in two blocks.

"redstone comparator"[4] - A two-mode device that either: 1) reads a variable-value signal from behind it IF that signal is stronger than the signal at the side inputs, or 2) it outputs the difference between the redstone levels (0-15) of the two inputs. This led to a LOT of interesting tricks and some VERY compact builds.

"pistons" - These are not redstone... but they extend one block when given an active signal, which can push a block that switches redstone. Most importantly, this lead to the invention FTL signals ("instant wire"[5]) by setting up a series of metastable pistons that should have retracted (they have lost their power), but have not been simulated yet. (they never received a block update; this is the basis of a BUD or Block Update Detector). By triggering updates at the first piston, you can trigger a cascade of updates that collapses the metastable system. Because this is just finishing updates that should have happened earlier and technically has nothing to do with redstone signaling, it can happen on the full 20Hz game clock ticks, and can cover any length in the same tick.

As this word processor demonstrates, it has now become possible to do some amazing things in redstone. I recommend the stuff done at OpenRedstone - their showcase[6] (now a year old!) briefly their VERY impressive builds, such as a PLA, function-plotters (w/ integration), a "torchless" (no NAND-gate) pipelined CPU, several games, and a maze generator. Oh, and an early version of this word processor. ^_^

If that's not complicated enough for you, you could always make rod-logic devices by creating many-block deep movement from the one-block-movement pistons.[7]

[1] https://www.youtube.com/watch?v=gbJ3HwNW0q8

[2] https://www.youtube.com/watch?v=yxAmphwLPDY http://www.minecraftforum.net/forums/minecraft-discussion/re...

[3] http://minecraft.gamepedia.com/Redstone_Repeater#Signal_lock...

[4] http://minecraft.gamepedia.com/Redstone_Comparator

[5] https://www.youtube.com/watch?v=uJeFLnD9Ctc

[6] https://www.youtube.com/watch?v=rg3rSOlauDk

[7] https://www.youtube.com/watch?v=FIf9Pxh9a-c