ClockworkGrue's writeup does indeed describe a block cipher, but his description is actually for a very specific subset of such ciphers. In particular, there is absolutely no requirement that a block cipher use matrix multiplication, the XOR operation, or even any S-boxes. His description seems heavily based on Square-like ciphers, like Square (obviously), Rijndael/AES, and Crypton. Others, like MARS, Serpent, and 3DES, have a significantly different structure internally. In addition, block ciphers themselves do not use initialization vectors at all. However, for various reasons, block ciphers are used in a so-called 'mode', which does tend to use an IV. Examples of modes are CBC and OFB modes.
So far, I've only told you what a block cipher isn't, not what it is. So what is it? It is simply this: a permutation of a set. Usually (OK, always) the cardinality of the set is a power of 2, for example 264 or 2128, though other sizes are also used occasionally. Since the set is of size 2n, we can act as if each of the elements of the set was an n-bit long string, and thus the block cipher is a permutation on fixed-size strings of bits (of size n).
A block cipher design is actually a specification for a family of such permutations, and the particular key used chooses a particular permutation out of the many possible permutations. Will we run out of permutations? Not likely. Even with relatively small 64-bit blocks (the smallest size that is considered at all safe), there are 264! possible permutations†. This number far, far exceeds the number of keys (which tends to range roughly from 240 to 2256). Basically, each block cipher stakes out a particular little area from this huge number of possible permutations, and they rarely (if ever) overlap.
There is an interesting aspect to this fact. If you had a block cipher with a large enough key (and we're talking freakin' huge), it would be possible to choose a key such that the cipher 'acted just like' another cipher. That is to say, the two ciphers would be the same permutation. With sanely sized keys, this will never happen, just because the number of possible permutations is too small for you to get a significant possibilty of overlap.
Block cipher design can be traced back to the work of Claude Shannon, who pointed out the essential aspects of a cipher must be confusion and diffusion. Confusion, in this context, means doing things that other people don't know about. This is generally done by combining the input (aka plaintext) with something derived from the key (for example by using addition or XOR). Diffusion is a somewhat more complicated idea, but one way to think about it is making sure that there is no obvious relationships between the plaintext and the ciphertext. This is done by using S-boxes, linear transformations, and a wide variety of other tricks.
Shannon never (AFAIK) actually designed a block cipher. Later on, Horst Feistel and others did the meaty design work when they created DES. More recent pioneers have been Vincent Rijmen and Joan Daemen, who created the Wide Trail Design Strategy, which underlies AES.
†: I might be mis-remembering this -- if I happen to be wrong let me know. Anyway, it's a really really really big number.
Block Ciphers
What the hell, let's make this a block cipher meta node of sorts. Not all of the links go anywhere useful, though most do. For the ones that don't, take it as a chance for a new writeup. Feel free to /msg me with more.