Let's consider a cryptographic algorithm (e.g. encryption) that uses a key. The key is part of a space of possible keys; e.g. the space of all sequences of 128 bits, for AES.
There is a conceptual attack known as brute force in which the attacker simply tries all possible keys until a match is found. This attack "works" for all algorithms, so, in order to achieve security, the key space must be large enough to make the cost of brute force ludicrous. Traditionally, we prefer it when the space of keys has size 2128 or more (in practice, 2100 would already be way beyond the technologically feasible, but cryptographers just love powers of two).
Symmetric algorithm usually accept keys as sequences of bits, where any possible sequence is a valid key. Thus, they can achieve the minimal key space requirement with a minimal number of bits: with keys of 128 bits, you can have 2128 keys, and they are all fine.
Asymmetric cryptography, on the other hand, tries to achieve something "magic". Symmetric algorithms are just mangling bits together in a kind of complicated knot; for asymmetric encryption or signatures, the only known methods involve mathematical structures. A consequence is that if keys for an asymmetric algorithm have a length of k bits, then not all sequences of k bits are valid keys.
Furthermore, the strength of the asymmetric algorithm relies on the intractability of the unraveling of the internal mathematical structure; for instance, in RSA, the public key is (mostly) a big composite integer, and the internal mathematical structure is the factorization of that integer into its prime factors. Attackers then usually have much better attack methods than simply trying out all possible private keys. For instance, a very primitive attack on RSA would enumerate possible divisors for the modulus, one at a time: for an integer n, the largest non-trivial divisor must of no greater than the square root of n, meaning that the basic "trial division" factorization algorithm will factor a 256-bit modulus in time 2128, not 2256. And we know of much better factorization algorithms.
The raw consequence is that asymmetric keys usually need more bits to express themselves: due to the internal structure, not all sequences of bits can be valid keys, and since there is an internal structure, attackers have better attack methods than brute force, thereby needing larger things.
Notwithstanding, most of the "key size" business is traditional. For instance, in the case of RSA, we say "RSA-2048" to mean "2048 bits", but that's just the size of the modulus, which is only one of the elements of the public key. The complete public key is a bit larger (to give room for the public exponent, which is usually short). The private key itself can be reduced to about half the size of the modulus (in that case 1024 bits), since if you know the public key (modulus n and public exponent e) and a non-trivial factor of n, then you can rebuild all the elements of the private key. However, it is traditional (and actually standard) to save private RSA keys as a bunch of integers that, for RSA-2048, would amount to more than 9000 bits, not counting encoding overhead.
Thus, the notion of "key size" for a cryptographic algorithm does not necessarily correspond to the actual encoded size of either the public or the private key, and it is always delicate to compare key sizes between different algorithms. For instance, "256-bit ECDSA" is usually considered to be stronger than "2048-bit RSA", even though:
- 256 is lower than 2048;
- RSA-2048 public keys will have size closer to 2100 bits, and private keys will be encoded over more than 9000 bits;
- 256-bit ECDSA public keys are normally encoded over 520 bits.
(Though a 256-bit ECDSA private key happens to be indeed a 256-bit integer — but with a strength somewhat equivalent to a 128-bit symmetric key, not a 256-bit, because of the internal mathematical structure.)
