For available flights to/from Baku check online table at navigator.az, this will give you an exact info on available flights and dates they fly.
AZAL (the Azeri national carrirr) has very acceptable Boeing 757 flights from major European cities (London, Paris, Milan, Frankfurt, Prague, Moscow). Major airlines have flights to Baku: BA, Lufthansa, Baltic Airlines, Austrian, Turkish Airlines, Qatar airlines. Many flights from Russia and CIS. Planes are rarely full except those flying from Russia. There are no direct flights from the Americas, Africa or Australia.
Asia-bound travellers can fly to Urumqi in western China (AZAL), Tashkent (Uzbekistan Airlines, twice a week), Dubai (AZAL).
THY (Turkish Airlines) is a very reliable carrier and offers competitive fares between European cities and Baku via Istanbul. However, direct flights by AZAL would be slightly cheaper.
Incredibly, buses run eight times daily Nakhchivan-Igdir-Istanbul (approx 30 hours, from $35). The main problems of this route are the spurious charges levied at the border and the challenge of reaching the rest of Azerbaijan from Nakhchivan (by flights only, $100 to Baku, advance booking highly recommended, 4 times/day), $50 to Ganja (4 times/week).
AZAL fly between Baku and Tbilisi. Overnight train (daily, 20:00 exiting Baku), a bargain at around $35 for place in 4 passengers kupe. It's quite bearable but can take 17-20 hours thanks to laborious, sometimes nerve-racking immigration/border procedures.
From Tbilisi's Ortajala bus station there is a nightly bus (sometimes minibus) to Baku. There are also morning services to/ from Tbilisi (Ortajala) and both Qax and Shaki. If you have time it is preferable to take a leisurely drive through Kaheti, cross the Lagodekhi border and arrive in Azerbaijan near Balakan. Minibuses from Tbilisi (Isani) leave when full to Lagodekhi via Tsnori (3-4hrs or go via Telavi.
If you're driving a car to Georgia you'll have to pay around $100 in insurance and short-stay road tax payments at the Customs department.
From/to Central Asia
The only direct option is an overnight Caspian ferry. This supposedly leaves nightly around 18:00 but in practice it departs at whim, maybe the next morning. It should take around 12 hours but can take three times that, the boat anchoring offshore if there is no berth available on arrival at Turkmenbashi. This can make a terrible bureaucratic mess if your hard-to-arrange Turkmen visa has fixed dates. Heavy winds can make the crossing unpleasant, or even dangerous. Berths cost $100 per person. Foot passengers must buy tickets at the Marine Passenger Terminal (Neftchilar avenue) opposite new Hilton & Marriott Hotels. However, the ferry departs from a separate dock, further east at Turkmenistanski Peron (cross Gagarin overpass, east end of Hacibayov Str) then walk 10 minutes south following the freight-rail tracks. If you want to take a vehicle you will need to buy the ticket and board the ferry at Nobel avenue (as of July 2012). On the Turkmen side the port is 6km from Turkmenbashi station whence there are cheap overnight trains to Ashgabat.
There are regular flights Baku-Aktau (Kazakhstan) on AZAL. Alternatively there's a ferry, however, the trip can take anywhere from 24-60 hours. The date and time of departure depends on finding enough cargo to load the boat so having bought a ticket you still need to enquire carefully and check regularly for changes in plan - once full the boat may suddenly depart unannounced. This is too unreliable option if you have limited visa time. Daily trains link Aktau to Aktobe/Aktyubinsk and Atirau on the main Kazakh-Russian rail network. There's a direct Baku-Atirau flight (Tue and Thur on IrtyshAvia). Also flights to Almaty, Tashkent, Bishkek available.
From/to Russia, Ukraine and Belarus
AZAL and many regional airlines fly to a wide variety of Russian and CIS cities. Competition is particularly fierce on the Baku-Moscow route. They service flights to St Petersburg, Minsk, Kiev , Donetsk, Kazan, Nizhny Novgorod, Perm, Tyumen, Samara, Ufa, Volgograd, etc. Check the link above for exact info.
The Russian land borders with both Azerbaijan and Georgia remain closed to foreigners. So at present ONLY LOCALS can take the trains that run from Baku to Russia. There are similar problems with Russia-Azerbaijan bus services.
There are flights to Tehran with AZAL and IranAir. The direct bus, Baku-Tabriz can take as much as 24 hours including border waits of four to seven hours so it's quicker and more comfortable to make the trip in hops to Astara, walk across the border then continue (easy and friendly). From Nakhchivan there is a direct train to Tabriz three times a week but it's quicker and easier to get a taxi to the border post at Culfa, then cross on foot to Iranian Jolfa which is a great base for visiting little-known Iranian Azarbaycan.