AES is a block cipher, actually three block ciphers.
A block cipher is a key-dependent permutation of values: it takes as input blocks (sequences of n bits for a given n; there are 2n such values) and outputs blocks of the same size. No two distinct input blocks will yield (for a given key) the same output block, and each of the 2n blocks is a possible output; that's what "permutation" means (it can be seen as a big shuffle of all the 2n values). The inverse permutation ("decrypt") can be efficiently computed (with the key, of course).
There are 2n! permutations over n-bit blocks; that's "factorial of 2n", a truly huge number: for n = 128, this is close to 1012963922773915897352048185492495741149019.37. The key "selects" which of these permutations is actually used. The block cipher is secure as long as this selection is "as if" it was random and uniform, i.e. we cannot distinguish the block cipher from a permutation which was selected randomly and uniformly in this large set.
Cryptographers tend to be practical people, so they want the key to be represented as a reasonably short sequence of bits; let's call k the size of the key. We want k to be large enough so that it is computationally unfeasible to enumerate of 2k keys. But since there are really many permutations to choose from, there is no problem in having very big keys.
We also want n (the block size) to be large enough in order to avoid some issues when the block cipher is used. Since a block cipher encrypts only blocks, it is rather inconvenient: when we encrypt, we usually want to encrypt messages with a variable and potentially large size. Thus come into play the mode of operation, aka "chaining mode", which specifies how a message is to be split into blocks, and how the encrypted blocks are glued back together. There are several modes; ECB is the simplest and it has weaknesses; CBC and CTR are the most widely used and they are OK... as long as we do not encrypt too many blocks with the same key. For n-bit blocks, trouble may appear once you process about 2n/2 blocks with the same key. We want n to be big enough, so that 2n/2 is so ludicrous that the situation will not arise.
Hence key size (k) and block size (n) are both dictated by security concerns, but not the same. In particular, there is no implicit rule that k and n should be equal to each other.
In 1997, NIST announced the AES competition: they wanted a secure and efficient block cipher to standardize. At that time, they had 3DES ("triple DES"), a block cipher with a 192-bit key and 64-bit blocks. The actual key size is lower: of the 192 bits, 24 are ignored right away, so the effective key size is rather 168 bits; moreover, the structure has a weakness which allows a theoretical attack with effort 2112, so 3DES is administratively said to offer "112-bit strength". That key size is still quite satisfying, but the existence of a known structural weakness is kind of worrying. More importantly, 64-bit blocks were turning out not to be enough: this implies a "chaining mode limit" at 232 64-bit blocks, i.e. 32 gigabytes. In 1997 multi-gigabyte hard disks were already common. So NIST said that they wanted the new block cipher to have 128-bit blocks (n = 128).
Also, in order to comply with some obscure military regulations, they wanted the block cipher to accept three distinct key sizes, so what NIST was asking for was really three block ciphers, but preferably three variants of the same underlying structure so that implementing all three in a given system remained cheap. The military regulations stated that there should be three "security levels", because these regulations were written at a time when cryptography was inherently weak and expensive, so the "strongest" methods were used quite sparingly (that was a time before the invention of the computer). NIST, in 1997, despite being a state organization, was smart enough to see that it could have already very good security with the smallest key size: there was no need to have a weak version of the cipher; they just needed some versions which could be claimed, in bureaucratic-speak, to be "stronger".
So NIST defined that the new algorithm(s) should accept keys of sizes 128, 192 and 256 bits. A 128-bit key is more than enough to ensure security in the foreseeable future. These sizes are multiples of 64, which is a power of 2, and programmers just love that.
Rijndael, the algorithm which was finally chosen as AES, complied to the competition rules like the other 14 candidates, and was specified with 128-bit blocks, and key sizes of 128, 192 and 256 bits. Actually, the Rijndael structure was also defined with blocks of size 192 and 256 bits, but NIST was not interested in such block sizes, and thus "AES" (the standard) is only with 128-bit blocks.
So the AES uses 128-bit blocks with a 192-bit or 256-bit key because:
- it was defined that way;
- that's what NIST asked for in the first place;
- it is sufficient for adequate security.
Note that having keys longer than blocks was already common before the AES (see 3DES, IDEA, RC2, RC5...).