Fly into the Kuban region with Kuban Air
Krasnodar has it's own (semi-inter)national airport and even it's home airline company: Kuban Air. For most outsiders (non-Russians) one will enter Russia through one of Moscow's airports and then can go on to Krasnodar (KRR). From Sheremethevo and Vnukovo the best connections are by Aeroflot, but highly recommended come Siber-Air flights from Domodedevo.
The Kuban region also has it's own aircraftcarrier: Kuban Airlines. This slowly rising airlines group is doing it's best to keep up with the bigger ones and already has direct connections with Cyprus, Istanbul (TRK) and Frankfurt (GER).
The best and fastest way to get to Krasnodar is traveling by air with Russian Airlines. I don't know weather it is expensive to get there by air or not but I know that for that money you can get a shopping tour for several days from Khabarovsk to China. It costs over 500$. The flight takes over 14 hours to get from Khabarovsk to Krasnodar with two landing in Irkutsk and Yekaterinburg.
Trains from Moscow to Krasnodar
Russia's railways are the largest network on rails in the world. The most famous track is no doubt the Trans Siberian and the most luxereous is the Red Arrow running between Saint Petersburg and Moscow. Lines down South often have destination Krasnodar in them and run frequently from Moscow (several a day). The distance is still around 1.400 km and the train takes a whole day to reach it's destination. One nighttrain makes the trip in (only) 17 hours, which still shows that Russian trains do not belong to the fastest in the world.
Trolleybus, bus, trams and "mashootki"
Getting around in Krasnodar is not that difficult, but one has to reckon with lingual problems if one travels alone and doesn't know the language. As the town is in surface quite big, distances are equaly long. Also, the town has a rather irregular shape with it;s centre pressed against the Kuban river and suburubs stretching out far into the vicinity. Public transport is all amazingly cheap, but the quality is below the standard that most will be used to. Old trolleybusses are added by minibusses (so called "mashootki") that carry the same numbers (lines) and are little more expensive, but drive much more frequently and are faster. The city has a several tram lines connected various parts together where trolleybusses do not run.
Taxi, official and unofficial
Traffic, like everywhere else in Russia, is a total chaos. Something that one will definately experience when one takes an official or unofficial taxi. This last category is a kind of carpooling-system, that is common in the whole of Russia. Stand besides the road, hold out your hand and someone will stop (soon). Make a deal for destination and costs and ... there you go. Also the official taxis are relatively cheap in contrast to other (Western) countries. The costs of taknig a taxi in Krasnodar often is the same as taking a bus in your home country (when living in US, Canada or (Western) Europe).
Get out of the heat on the river Kuban
The Kuban river is the main river of this region. It runs from the Caucasus mountains winding through the Kuban land to end up in the Azov sea near Temryuk. Krasnodar was founded at the Northern banks of this river and it's water is epecially in summertime a blessing. Not only fo swimming (watch out, many spots are forbidden to swim), but just to be in the neighborhood or ... on top! Riverboats have organised tours over the river, sailing on the water between Krasnodar city and the autonomous republic within Russia: Adegya.