How is there enough $\ce{O2}$ in the atmosphere to breathe if you are in a desert with no plants?

Humans depend on $\ce{O2}$ for breathing. The source of $\ce{O2}$ is photosynthesis by plants or cyanobacteria in the ocean.

How is it, that when people travel through deserts or the Arctic / Antarctica, they able to breathe? Is it due to Earth's wind currents blowing $\ce{O2}$ from the nearest ocean?

The short answer is, $\ce{O2}$ is all around us!

You aren't breathing the $\ce{O2}$ that the trees next to you are respirating (at least not much). No matter which way the wind is blowing, you will have sufficient oxygen content. A "can't breathe" feeling comes from inhaling pollutants or extremely dry air (in which case you need to drink more water). Unless, of course, you are so far up in the atmosphere that there is simply less atmosphere to breathe (e.g. lower atmospheric pressure).

As you can see in the image below, the $\ce{O2}$ molecule abundance in the atmosphere is a giant reservoir that extends far up into the atmosphere. $\ce{O2}$ and $\ce{N2}$ are evenly mixed throughout the entire atmosphere, even beyond the stratosphere. Thus, the abundance of oxygen in the lower atmosphere is not really a local phenomenon.

Most of the free oxygen available is due to ancient oceanic phytoplankton, and they are still producing! While there are fluctuations in the oxygen abundance of the atmosphere on a geological time scale, there is no shortage of $\ce{O2}$ since there is an overwhelming amount of production.
For a quantitative breakdown of the oxygen production/consumption, see https://en.wikipedia.org/wiki/Oxygen_cycle

****Vertical profiles of the mixing ratios of selected species at the equinox****

R. M. Goody and Y.L. Yung, Atmospheric Radiation, Theoretical Basis, OUP, 1989.

This wikipedia article has a great discussion of the topic: https://en.wikipedia.org/wiki/Geological_history_of_oxygen

Before photosynthesis evolved, Earth's atmosphere had no free $\ce{O2}$. Photosynthetic prokaryotic organisms that produced $\ce{O2}$ as a waste product lived long before the first build-up of free oxygen in the atmosphere, perhaps as early as 3.5 billion years ago. The oxygen they produced would have been rapidly removed from the atmosphere by weathering of reducing minerals, most notably iron. This 'mass rusting' led to the deposition of iron oxide on the ocean floor, forming banded iron formations. Oxygen only began to persist in the atmosphere in small quantities about 50 million years before the start of the Great Oxygenation Event. This mass oxygenation of the atmosphere resulted in rapid buildup of free oxygen. At current rates of primary production, today's concentration of oxygen could be produced by photosynthetic organisms in 2,000 years.

Since the start of the Cambrian period, atmospheric oxygen concentrations have fluctuated between 15% and 35% of atmospheric volume. The maximum of 35% was reached towards the end of the Carboniferous period (about 300 million years ago), a peak which may have contributed to the large size of insects and amphibians at that time. Whilst human activities, such as the burning of fossil fuels, have an impact on relative carbon dioxide concentrations, their impact on the much larger concentration of oxygen is less significant.

Look at it this way: According to the American National Center of Atmospheric research, the Earths atmosphere weighs 5.148 x 10^^18 kg., and that atmosphere is composed of about 20.8 to 20.9% oxygen (depending on moisture content of the air). So the Earths atmosphere contains about 1.07 million trillion kgs of oxygen.

The 7.5 billion (or so) humans on the planet, each converts an average of about 0.73 kg of oxygen per day, converting most of it to exhaled CO2. So the planetary consumption of oxygen by humans, as a percentage of the total available, is about 100 x 0.73 x 10^^9 / 1.07 x 10^^18 %.

That is, about half of one millionth of 1% of the Earths available oxygen, a level of oxygen deficiency that is almost instantly dispelled by turbulent mixing in the troposphere (i.e.by 'weather'). So no, there is no chance of gasping for oxygen in deserts or polar wastes.

Now gasping for air 8000 metres up a mountain, or in a crowded disco with cigarette smoke and poor ventilation - that is another question!