Recommended: Pulkovo or Aeroflot domestic flight are rather cheap when combined with a ticket to/from either Saint Petersburg or Moskva. Kuban-air has also connections with all mayor cities in Russia, however quality of the airplanes leave many wishes (and questionmarks about the safety). They have one connection with WEstern Europe (Frankfurt am Main - Germany.
Russian railways have a dense (dense, in contrast to the countries desity!) network of tracks. However, comfort and luxery are of different proportions then in long-distance training in Europe or North America. The traisn are thereby rather slow and it takes almost two days to travel the distance (1300 km) from Moskva to the Kuban. A faster train is now running, but busy (make reservation far in advance) and more expensive.
Public transport in larger towns is pretty good. Russian way of getting around is a kind of hitchhiking or carpooling. You can see it everywhere along the road. The Russians with a car try to lower their costs by offering these 'hitchhikers' a ride against relatively low prices that they agree on the street. In this way you can even travel all over Kuban, however a tight timetable can - of course - not be maintained. Throughout the Kuban, public transport is mediocre and finding out when which buss drives to what destination is complicated and takes a lot of time. Sometimes, renting a car is the best solution for getting around in the Kuban, but ... take into consideration that rental prices for non-Russians are incredably high.