Dagestan is a region of Russia in the North Caucasus bordering Chechnya and Georgia to the west, Stavropol Krai and Kalmykia to the north, the Caspian Sea to the east, and Azerbaijan to the South. Due to its own instability and its proximity to Chechnya, Dagestan is an unsafe travel destination, but travel is possible for the intrepid.
Dagestan shares with its Caucasian neighbors the towering mountains of the Greater Caucasus, rushing Caucasian rivers, and spectacularly situated stone auls (mountaintop villages). But in an already diverse region, Dagestan is a wonderland of ethnic and cultural diversity. About 35 separate ethnolinguistic groups live in this Scotland-sized republic and the region contains an amazing 12 language families! For all this cultural diversity, Dagestanis are fairly united in their Islamic religion — virtually all non-Russian ethnic groups are Muslim.
Makhachkala will almost certainly be your first destination, whether by plane from Moscow, or by train via Rostov-on-the-Don through Mineralnye Vody. Note that security is very tight at the Makhachkala airport.
Within the 7 language families of the Dagestanian language grouping alone there are about 30 languages, many of them considered among the most difficult in the world to master. Fortunately, everyone, regardless of nationality, understands the lingua franca, Russian. Azeri is also widely used in the southeast Caspian region around Derbent; those who speak Turkish may be able to make themselves understood in this area.
Dagestan is not a safe tourist destination by any stretch of the imagination. The mountainous areas of the republic (i.e., the most interesting areas) have seen major military operations in recent years between various groups and the Russian military. Criminal activity is widespread throughout the region, often targeting the few foreign tourists that do continue to visit for kidnapping, extortion, and worse. Dagestan shares along with the rest of the North Caucasus an extravagantly corrupt official culture and bribes and harassment are business as usual.
If you'd like to catch a glimpse of Dagestani culture and beauty, check online for a copy of the late Sergei Bodrov's haunting film, Prisoner of the Mountains (Кавказский пленник), which was shot in a Dagestani mountain aul, hiring the villagers as extras.
Dagestan is a predominantly conservative Muslim region with very strong chivalric mountaineer traditions. Be careful not to insert yourself into local politics or to insult locals' sense of honor, or you might find yourself estranged in a strange land.
In Dagestan there are three federal GSM operators (MTS, Beeline, Megafon) and one dagestanian operator "Dagestanskaya Sotovaya Svyaz" and they often have offers that give you a SIM card for free or at least very cheap. If you are planning to stay a while and to keep in touch with Dagestanian and other North-Caucasus people, then you should consider buying a local SIM card instead of going on roaming. If you buy a SIM card from a shop you'll need your passport for identification. It only takes five minutes to do the paperwork and it will cost less than $10. Visitors should know that there is no real embassy or consulate in Dagestan. Your best bet would be Moscow in Russia, Tbilisi in Georgia, Baku in Azerbaijan, or Yerevan in Armenia. Good luck!