First point: there is a practical security increase only if both encryption algorithms, taken alone, would be independently vulnerable to exhaustive search, i.e. by using too small a key. That is the main issue, and it is better to fix that. Exhaustive search works only up to the key sizes such that the space of key can be enumerated with existing or foreseeable technology. There are good reasons why a 128-bit key would resist such attempts. Thus, if you use a decent encryption algorithm, there is no need to "double" it. There is no security level beyond "cannot break it": you cannot not-break an algorithm more than "not at all".
Doubling or tripling algorithms has been used in older days to reuse previous algorithms which were definitely too weak on their own; the prime example is Triple-DES (aka "3DES"), built over the previous DES. DES and its 56-bit key space is vulnerable to exhaustive search (it has been done). As @CodesInChaos points out in his comment, doubling and tripling don't give you your money worth: double-DES would use 112-but keys, but would not offer 112-bit security.
In a nutshell, for double-DES, the attacker would encrypt the known plaintext with the first DES and all possible keys k1 (256 possibilities), and also decrypt the known ciphertext with all possible keys k2 (256 possibilities again), and then look for a match in the two sets of 256 "intermediate values". Matching will have cost about 2·56·256, i.e. about 263 (that's the cost of sorting the two sets, so that matches are detected with a linear search). With a merge sort, the sorting-and-matching steps only require linear access, thus compatible with hard disks. We are talking here about 257 128-bit values (two known plaintext blocks, so that there won't be ambiguity about the keys), aka 261 bytes, aka 2 millions of terabytes. One million hard disks is expensive... but technologically doable, contrary to a 2112 exhaustive key search.
Therefore, doubling algorithms does not bring that much of a benefit. Tripling increases security when beginning with weak algorithms (at least when the weakness is only about key size), but, there again, not as much as the invested effort (with 3DES, you have 168 bits of key, but resistance is "only" up to 2112). Of course, tripling also means dividing performance by three, which may or may not be tolerable in any given context. Tripling, quadrupling... does not fix other issues, such as blocks which are too small (3DES still uses the 64-bit blocks of DES, which means that serious issues arise when encrypting about 232 blocks worth of data with a given key, i.e. about 32 gigabytes, which is not much by today's standards).
It is much better to start with an encryption algorithm (like AES) which does not have exhaustive search issues to begin with, making doubling or tripling useless. Doubling (or tripling) algorithms is like a pegleg: it helps you keep upright if you had the misfortune of losing a leg; but, if possible, it is better to keep your two biological legs.