The quickest, safest and the most reliable means of transport in Dagestan is the so called marshrutka, i.e. a minibus. They run both in larger towns and connect different places in Dagestan. The capital city Makhachkala, the republic’s biggest transport junction, has two stations – the northern one (there you can find marshrutkas going to such cities as Kizlyar, Khasav-Yurt and to most of the mountainous regions) and the southern one (marshrutkas going to Derbent and southern Dagestan). Marshrutkas rarely leave at the appointed time. They usually set off when they are fully booked. You should also bear in mind that when it comes to some remote mountainous regions, marshrutkas leave very early in the morning and do not park at the station itself, but somewhere in the vicinity. Therefore, it is advisable to go to the station on the day before the departure and find out where and when you should turn up. The best thing is to make arrangements with the driver for the next day. You can also get from Makhachkala to larger cities by regular buses.
Dagestan is also crossed by the railway running from Azerbaijan to Russia, so theoretically you can get e.g. from Derbent to Makhachkala by train. However, this is extremely time-consuming and you’d better not be bothered about it.
Another good way to travel is hitch-hiking. You should keep in mind, though, that in Russia drivers expect some payments for it, and therefore it is better to negotiate the price before you get in. In the mountains you will usually get a ride for free.
Some places in Dagestan can only be reached by off-road vehicles (they usually run from the capitals of the regions), on horseback or on foot (only mountainous paths lead there).
A hike across Dagestan would be a great idea. However, there are no accurate maps of the republic and no marked out mountain routes; you should stick to the roads that connect towns and villages that can be found on the map. There are very few asphalt roads, but when you walk dirt roads, you will come across truly amazing landscapes.