The Hijaz is the region of what is now the western Saudi Arabian desert around the cities of Medina and Mecca, including the cities of Jedda and At Ta'if.
It starts on the eastern side of the Red Sea just beyond the mountains and peters out somewhere in the desert of the central Arabian peninsula. Its closest southern neighbor is Yemen, while to the north it's Iraq, Palestine, and the area around the Sinai peninsula. Although it doesn't exactly have borders as such, the Hijaz would not actually border any of these places if it did since it exists around a few oasis towns in the middle of the Arabian desert.
Over time, a number of powers have held sway over this rather isolated area. Up until the rise of Islam, some transitory kingdoms periodically subjected the area, but for the most part the native Arabs lived in fairly stateless circumstances. Although bordered by both the Sasanians and the Byzantines to the north, during the time of Mohammed the Hijaz was governed only by whichever clan or group could provide order, if one could. A reasonably large portion of the population were nomadic Bedouins, since the desert didn't support the sedentary except in exceptional places like oases.
Since Mohammed's attentions on the cities of Mecca and Medina conferred holy status on those cities, they became very desirable very quickly in spite of their isolation. The Hijaz held the seat of the caliphate until the establishment of Baghdad after the Third Fitnah. In 1258 the region came under control of the Egyptian Fatimids, who held it until 1517 when the Ottomans took it from them. When the Ottoman power in the area began to collapse in 1916 during World War I, the Hijaz declared itself to be independent. That didn't last all that long, though, as the neighboring kingdom of Najd conquered it ten years later. In 1932, the Hijaz became a part of Saudi Arabia, where it has remained ever since.
Sources: http://www.lexicorient.com/e.o/hijaz.htm, as well as the Cambridge Illustrated History of the Islamic World and Marshall Hodgson's Venture of Islam, book one.