There are two main advantages to choosing the exponent 2¹⁶+1.

The first advantage, as Johannes observed, is that for fixed size exponent, exponentiation to power e using the basic repeated squaring method is moderately faster when e has lots of zero bits. It is not true that exponents with more one bits are necessarily slower since there are plenty of such numbers with very short addition chains (though finding such short addition chains is an NP complete problem in general). In any case, if this were the only constraint then e = 3 would be a much better choice than e = 2¹⁶+1.

The second advantage is that 2¹⁶+1 is a prime number and it is not too small. A requirement of the RSA algorithm is that the exponent e must be relatively prime with φ(pq) = (p-1)(q-1). Since the large primes p and q are chosen randomly, there is always a chance that (p-1)(q-1) is not relatively prime with the (previously chosen) exponent e and the primes p,q must therefore be discarded. So e = 3 is a very poor choice since it is expected that every third choice of p and q would be a bad one. Choosing e to be a prime makes the probability of picking bad p and q around 1/e. So choosing e to be a large prime would be best, but too large an e would make exponentiation slow. In the end, e = 2¹⁶+1 is a nice compromise value.

There are a two minor advantages to choosing the exponent 2¹⁶+1.

The first advantage, as Johannes observed, is that for fixed size exponent, exponentiation to power e using the basic repeated squaring method is moderately faster when e has lots of zero bits. It is not true that exponents with more one bits are necessarily slower since there are plenty of such numbers with very short addition chains (though finding such short addition chains is an NP complete problem in general). In any case, e = 3 would be a much better choice than e = 2¹⁶+1 for the sole purpose of exponentiation.

The second advantage is that 2¹⁶+1 is a prime number and it is not too small. A requirement of the RSA algorithm is that the exponent e must be relatively prime with φ(pq) = (p-1)(q-1). Since the large primes p and q are chosen randomly, there is always a chance that (p-1)(q-1) is not relatively prime with the (previously chosen) exponent e and the primes p,q must therefore be discarded. So small exponents e are poor choices since about every (e-1)^th choice of p and q is a bad one, thus shrinking the overall key space. Choosing e to be a large prime would be best, but too large an e would make exponentiation slow. In the end, e = 2¹⁶+1 is a nice compromise value.