The Hajj can only be completed during the Islamic month of Dhu al-Hijjah. A pilgrimage to Mecca at any other time is known as Umrah (عمرة), and while not compulsory is highly recommended.
The Hajj is one of the five pillars of Islam; every adult Muslim is supposed to do it at some time in his or her life if health and finances permit. In poorer areas it is not uncommon for whole families or even whole villages to chip in to send one person.
It is also one of the largest human migrations. Every year over two million people visit Saudi Arabia for this pilgrimage. Since they all arrive at roughly the same time and visit the same places in the same order, and since a large number of Saudis go as well, this is a major logistical problem. The Saudi government has a ministry to manage it.
Nonetheless, a few Western explorers have managed the journey — most notably, Sir Richard Burton made the Hajj in 1853 and wrote an account of the trip.
Unless you are a citizen of Saudi Arabia you will need a visa, obtained in advance from a Saudi embassy. Visas are allocated on a quota system, based on the number of Muslims in a country. You may need to provide evidence that you are Muslim, such as a letter from your local mosque.
Women under 45 are required to travel with a mahram, a related adult male who is the head of her family (usually a husband or father), and proof of the relationship is required. Women over 45 may travel without a mahram if they're in an organized group and have a letter of permission from the man who would be her mahram.
Proof of vaccination for meningitis (specifically the ACYW135 vaccine) between three years before and ten days before your entry into Saudi Arabia is required. Yellow fever vaccination is required if you arrive from any country with known yellow fever infections, and polio vaccinations are required for children up to 15. As millions of people from all over the world gather for Hajj and therefore you will be exposed to many diseases, you may want to discuss other vaccinations and preventative measures with your doctor.
Historically, people made the pilgrimage by camel caravan or by ship. It took months, even years, and was very dangerous.
Today, most pilgrims arrive via the airport at Jeddah. There are two special Hajj terminals, the largest buildings (by roof area) in the world. They are enormous tents of fiberglass fabric on reinforced concrete poles and steel cables. At Hajj time, there are dozens of large aircraft parked alongside these terminals.
From Jeddah — for most pilgrims, directly from the airport — there are buses to Mecca. Buses are also used for the trip to Medina; Saudi Arabia has not had a railway since Lawrence and the lads blew up the Turkish one during the First World War.
Once at Mecca, the traditional Hajj route is as follows:
The first two steps are known as the "lesser Hajj" or Umrah, while the full course is known as the "greater Hajj" or al-Hajj al-Akbar.
Hajj and Umrah visas are strictly limited to Mecca, Medina, Mina, Arafah and Muzdalifah. Traveling anywhere else in Saudi Arabia will require an additional travel permit, which is difficult and time-consuming to obtain, and is rarely granted without good reason (eg. medical emergencies).
Expats living in Saudi Arabia can get good deals on flights out of the country at Hajj. With all the pilgrims coming in, airlines from any country with a lot of Muslims — most places between Nigeria and Indonesia — offer large discounts to avoid flying home with empty planes.