You've decided to use public key cryptography, and you need to know what size numbers you should use in your system. For example, if you want to use RSA, should you use 512bit RSA or 4,096bit RSA?
There's some debate on this issue. When using RSA, we recommend a 2,048bit instantiation for generalpurpose use. Certainly don't use fewer than 1,024 bits, and use that few only if you're not worried about longterm security from attackers with big budgets. For DiffieHellman and DSA, 1,024 bits should be sufficient. Elliptic curve systems can use far fewer bits.
The commonly discussed "bit size" of an algorithm should be an indication of the algorithm's strength, but it measures different things for different algorithms. For example, with RSA, the bit size really refers to the bit length of a public value that is a part of the public key. It just so happens that the combined bit length of the two secret primes tends to be about the same size. With DiffieHellman, the bit length refers to a public value, as it does with DSA.^{[1]} In elliptic curve cryptosystems, bit length does roughly map to key size, but there's a lot you need to understand to give an accurate depiction of exactly what is being measured (and it's not worth understanding for the sake of this discussion?"key size" will do!).
^{[1]} With DSA, there is another parameter that's important to the security of the algorithm, which few people ever mention, let alone understand (though the second parameter tends not to be a worry in practice). See any good cryptography book, such as Applied Cryptography, or the Handbook of Applied Cryptography, for more information.
Obviously, we can't always compare numbers directly, even across public key algorithms, never mind trying to make a direct comparison to symmetric algorithms. A 256bit AES key probably offers more security than you'll ever need, whereas the strength of a 256bit key in a public key cryptosystem can be incredibly weak (as with vanilla RSA) or quite strong (as is believed to be the case for standard elliptic variants of RSA). Nonetheless, relative strengths in the public key world tend to be about equal for all elliptic algorithms and for all nonelliptic algorithms. That is, if you were to talk about "1,024bit RSA" and "1,024bit DiffieHellman," you'd be talking about two things that are believed to be about as strong as each other.
In addition, in the block cipher world, there's an assumption that the highly favored ciphers do their job well enough that the best practical attack won't be much better than brute force. Such an assumption seems quite reasonable because recent ciphers such as AES were developed to resist all known attacks. It's been quite a long time since cryptographers have found a new methodology for attacking block ciphers that turns into a practical attack when applied to a wellregarded algorithm with 128bit key sizes or greater. While there are certainly no proofs, cryptographers tend to be very comfortable with the security of 128bit AES for the long term, even if quantum computing becomes a reality.
In the public key world, the future impact of number theory and other interesting approaches such as quantum computing is a much bigger unknown. Cryptographers have a much harder time predicting how far out in time a particular key size is going to be secure. For example, in 1990, Ron Rivest, the "R" in RSA, believed that a 677bit modulus would provide average security, and 2,017 bits would provide high security, at least through the year 2020. Ten years later, 512 bits was clearly weak, and 1,024 was the minimum size anyone was recommending (though few people have recommended anything higher until more recently, when 2,048 bits is looking like the conservative bet).
Cryptographers try to relate the bit strength of public key primitives to the key strength of symmetric key cryptosystems. That way, you can figure out what sort of protection you'd like in a symmetric world and pick public key sizes to match. Usually, the numbers you will see are guesses, but they should be as educated as possible if they come from a reputable source. Table 71 lists our recommendations. Note that not everyone agrees what numbers should be in each of these boxes (for example, the biggest proponents of elliptic curve cryptography will suggest larger numbers in the nonelliptic curve public key boxes). Nonetheless, these recommendations shouldn't get you into trouble, as long as you check current literature in four or five years to make sure that there haven't been any drastic changes.
Desired security level 
Symmetric length 
"Regular" public key lengths 
Elliptic curve sizes 

Acceptable (probably secure 5 years out, perhaps 10) 
80 bits 
2048 bits (1024 bits in some cases; see below) 
160 bits 
Good (may even last forever) 
128 bits 
2048 bits 
224 bits 
Paranoid 
192 bits 
4096 bits 
384 bits 
Very paranoid 
256 bits 
8192 bits 
512 bits 

Until recently, 1,024 bits was the public key size people were recommending. Then, in 2003, Adi Shamir (the "S" in RSA) and Eran Tromer demonstrated that a $10 million machine could be used to break RSA keys in under a year. That means 1,024bit keys are very much on the liberal end of the spectrum. They certainly do not provide adequate secrecy if you're worried about wellfunded attackers such as governments.