Are phone calls on a GSM network encrypted?
For the most part[1] they are encrypted, but not sufficiently enough to be considered as safe, tap resistant encryption. GSM uses 64-bit A5/1 encryption that is weak, to say the least. $15 phone, 3 minutes all that’s needed to eavesdrop on GSM call article from ArsTechnica covers it pretty well IMO, if you care to read more about it.
However, it also depends on what you mean by GSM. What I mentioned above is true for what we usually mean as GSM (2G, or second generation protocols). 3G are generally considered slighly safer (for lack of a better word):
3G networks offer greater security than their 2G predecessors. By allowing the UE (User Equipment) to authenticate the network it is attaching to, the user can be sure the network is the intended one and not an impersonator. 3G networks use the KASUMI block cipher instead of the older A5/1 stream cipher. However, a number of serious weaknesses in the KASUMI cipher have been identified.
https://en.wikipedia.org/wiki/3G#Security
However:
Many operators reserve much of their 3G bandwidth for internet traffic, while shunting voice and SMS off to the older GSM network.
http://arstechnica.com/gadgets/2010/12/15-phone-3-minutes-all-thats-needed-to-eavesdrop-on-gsm-call/
[1] Unencrypted communication (flag A5/0) is also supported on GSM systems, and this encryption (or lack thereof) might be regulated by laws of different countries differently, or part of the carrier's policy not to use it. Some devices also display notifications to users when their calls will be encrypted and when not, but most probably felt it's hardly worth bothering notifying users, especially considering the strengths of various cypher suits in use with GSM protocols. See my reply to @HSN's comment below for more information.
Yes, all GSM calls use an A5/1 stream cipher. It has been found that this is fairily easy to decrypt using a Rainbow Table. Additionally, the FBI admits to intercepting all phone conversations in the US.
So yes, it is encrypted, and cell phone companies don't give a damn about your privacy. If you care about privacy, you should use RedPhone and TextSecure which is an open source projects by Whisper Systems (now apart of Twitter).
Calls over GSM might be encrypted. The phone and the base station initially agree whether to encrypt at all and if which algorithm to use. The phone sends a list of supported ciphering algorithms to the base station. The base station sends a 'Cipher Mode Settings' element (see GSM 04.08 Chapter 10.5.2.9) to the phone. This element holds one bit that marks if encryption should be used. If encryption should be used, there are three bits that define the used algorithm:
0 0 0 cipher with algorithm A5/1
0 0 1 cipher with algorithm A5/2
0 1 0 cipher with algorithm A5/3
0 1 1 cipher with algorithm A5/4
1 0 0 cipher with algorithm A5/5
1 0 1 cipher with algorithm A5/6
1 1 0 cipher with algorithm A5/7
1 1 1 reserved
Speaking of the security, there was a practical attack against A5/1 shown by Karsten Nohl. A5/2 is weak and was withdrawn by the GSMA (see Wikipedia). At least some providers nowadays support A5/3 (example: Deutsche Telekom in Germany or Proximus in Belgium). A5/3 is based on KASUMI that is also used for 3G. To my knowledge, A5/4 to A5/7 are not (yet) defined.