To begin, it's important to understand the background of Arabic as a language before this can be answered.

Modern Arabic is less one language than it is a dialect continuum. Essentially this means that there are overarching similarities in the languages spoken throughout MENA, however, the day to day Arabic dialect spoken by someone in Morocco is far enough away from the day to day dialect spoken in Saudi Arabia that it's not perfectly mutually intelligible. This is common in many places outside of the Arab world too, and generally people from different regions within the Maghreb & Middle East will communicate with one another using a standardised vocabulary which is based on Egyptian Arabic, or use a constructed Arabic known as Modern Standard Arabic in formal situations.

If you decide to learn Arabic, Egyptian is typically the dialect that you'll start with rather than MSA due to the unnecessary complexity and jarringly formal nature of the latter. Due to the Egypt's political status during the 20th Century and the country's dominance of music, film and television in the region, the dialect has become the standard form. Compare this to the midwestern dialect in the US or 'BBC English' in the UK, used in much the same way in their respective locales.

In more formal situations and when it comes to writing, however, it's far more common to use MSA and very unlikely that individuals will defer to the dialect of another country. MSA is based on Classical Arabic which was spoken around the time of Mohammad, with changes to structure and vocabulary that reflect modern usage, but with the majority of linguistic features maintained. Due to the interconnection of religion and language in the region, MSA and CA, which are considered the same language (but different formality registers) by speakers, are taught from a young age and prevalent throughout day to day life.

To go back to the question, Arabic speakers in MENA don't all speak the same language, but similar dialects within one family. Due to both religion and necessity of communication, Classical Arabic has been modernised and standardised to create a formal spoken and written language that traverses these borders. This essentially places Arabic in its historical form as a regional lingua franca rather than modern Arabic being a homogenous and singular dialect as is often assumed. This is similar, but not identical to, Latin in the Christian world, which enjoyed special status as lingua franca across science and communication long after the vulgarisation and diversification of the language in common usage throughout previously Roman Europe.

TL;DR: Classical Arabic has been standardised as a way of communicating across dialects and is taught in schools across the Middle East and North Africa.

Edit: For non-Arab muslims there are also a myriad of translations of the Qur'an much like the Christian Bible or Torah.

I'd like to add to /u/stevewastaken's comment because I think it's right in the main but there are some things I would dissent from--for one thing I'd be really curious to know where in his experience students of Arabic are first introduced to Egyptian Arabic. Al-Kitab is pretty much the standard Arabic learners textbook in every Arabic program I've come across and that's almost entirely Modern Standard Arabic. Egyptian Arabic's status as a "standard" dialect has also in large part disappeared with the advent of dedicated pan-Arabic media like al-Jazeera. Even Disney, which once did all of its cartoons in Egyptian dialect, now does them in MSA.)

In technical terms, what he is describing is that Arabic is a "diglossic" language. This term was originally used to refer to the distinctions between ancient and modern Greek, but it's a frequently discussed term in Arabic linguistics. It's not an entirely adequate word because the "di-" suggests that it's a binary (MSA or Classical vs. Dialectic) which isn't accurate. El-Said Badawi, for example, proposed a five-tiered system of Arabic ranging from "illiterate colloquial" to classical.

One of the defining cultural features of Arabic, however, is that the written language is always MSA/Classical. A handful of modern (and often self-consciously modernist) Arab authors have toyed with this convention, but it's sufficiently rare that novels written entirely in colloquial Arabic as recently as 1994 could draw enough of a stir to warrant scholarly articles about them that included summaries of the entire corpus all-colloquial literature which include, in total, 30 fictitious autobiographical works, one genuine autobiography, and three novels. That's it. Across 1400 years of Arabic writing in Egypt.

Now, why is this?

In large part it has to do with the social status of Arabic and literacy in the Arabic-speaking world. There is some dispute about what medieval literacy rates would have been, so I don't want to generalize, but to the extent that an average person attained basic literacy that literacy itself would be almost entirely based on their ability to read, recite, and reproduce passages of the Qur'an.

Functional or advanced literacy would have been far more restricted, however, and would generally have been confined to the religious scholarly class--the ulema-- or to the often largely overlapping bureaucratic class. The form of education that produced these classes was almost entirely based on knowledge, memorization, and understanding of classical Arabic texts, typically including the ability to memorize thousands of hadiths and their accompanying isnads.

Though I'm not an expert in either of these the result as I understand it would have been comparable to the scholarly classes of China, where knowledge of ancient classical texts was the most relevant criterion for success, or in medieval Europe where writing in Latin predominated among the scholarly classes even when the vernacular languages no longer bore any resemblance whatsoever to Latin.

While this monopoly on education has largely been broken in the past 200 years, the idea that written Arabic should still be in MSA or Classical remains.

This persists for a number of reasons, some of them aesthetic or cultural, while others are religious or ideological.

For one thing, the only term that exists in Arabic itself for "correct" Arabic is the term "الفصحى" "fusha" (pronounced FOOS-ha) which properly denotes only classical Arabic and not "MSA" which doesn't itself have any set term or defining set of characteristics that in any way makes it a "standardized" form of "modern" Arabic. The aesthetic connotations of this can be found by looking at what fusha means. Among dictionary definitions of various verb forms of the root letters fa-sa-ha in Arabic are: "to be eloquent", "to bring into literary form", "[to] make correct Arabic", "purify the language", "to express oneself in flawless literary Arabic", and so on.

To give one example of the religious issues involved in moving away from the Qur'an as the basis for written Arabic is that if you believe, as Muslims do, that the Qur'an is the perfected word of God, then it follows that there cannot be any grammatical mistakes in the Qur'an. Therefore the Qur'an, a religious book, is also the ultimate grammatical authority: if a construction appears in the Qur'an, it is ipso facto correct.

While the strictly religious nature of the educational elites in Arab society has been alleviated, the biases regarding the ability to produce "correct" Arabic in a classical style have not. This actually poses an enormous problem for education systems in the contemporary Arab world, because in order to produce students who can actually write in correct classical Arabic requires an education system focused on that particular outcome, and many countries would rather produce students who are, say, fluent in English or French, or can do computer programming.

I think I can speak from some personal experience in spending most of my career working in bilingual Arabic/English environments that the result that there is almost inevitably a tiered staffing arrangement of those Arabic speakers who can actually compose written Arabic for publication and those who cannot, and the differences tend to be stark.

To bring this back to your original question, I think I would summarize the current state of affairs in Arabic as follows: while there is a greater degree of mutual intelligibility between classical Arabic and contemporary dialectical Arabic than there is between, say, Old English and Contemporary English, the gap is probably actually not that much further than between Shakespearean English and Contemporary English. Nonetheless, the difference in difficulty/familiarity that you experience as an English speaker is in large part the result of the relative lack of importance that Shakespeare holds on either the standardization of the language, or on the relative measure of an individual's education compared with the role that the Qur'an or classical Arabic plays for native Arabic speakers. I think I can say with confidence that if your ability to advance in society or to be viewed as literate entirely depended on your ability to reproduce Elizabethan Shakespearean grammar/syntax/vocabulary that you would be able to do so with very little difficulty. Nonetheless, in the Arab world today this is to some extent changing, with the result that while native, highly educated speakers might understand classical texts, depending on the type of education they received they may not be able to reproduce them.