There is daily overnight train service between Azerbaijan and Georgian capitals. The train departs from Baku for Tbilisi at approximately 21:00-22:00 and scheduled to arrive 16 hours later at around 12:00-13:00 pm next day (there is one hour difference between the two countries). The cost is around $50 USD (42 AZN) for 1st class ticket and about half for 2nd class ticket. A daily overnight train from Tbilisi to Baku departs usually at 17.00 and arrives to Baku at 8.00 am next morning. Train might be pretty full and very hot but quite confortable.
To buy train tickets in Baku, the train station is next to the 28 May metro station. Look for a doorway marked "Kasse" to buy tickets. The trains are behind that area, you have to go around to reach them.
Be prepared to spend a great deal of time at Azerbaijan/Georgia border. Border crossing lasts about 1.5 hours for both sides. You should reach the border at around 10am. Make sure you have your visas arranged in advanced.
At the two-hour stop entering Georgia, taxi drivers mass outside the train offering rides into Tbilisi. Good bargainers can catch a ride for about 35 lari and arrive in the city by 11:00 or earlier instead of at the scheduled 12:00 or 13:00.
Alternatively, there is a nightly train to Balakan via Sheki. It leaves Baku at 10:20 pm (summer schedule). Arriving in Sheki at around 7, Qax around 9, Zaqatala around 11 and Balakan around 12. It cost 3 Manat for 3rd class, 4 manat fro 2nd class and 8 manat for 1st class. You can exit at Balakan and cross the border in the morning. Plenty of taxis & buses available at Georgina side of the border that will take you to Tbilisi (1.5 hours drive).
NOTE: 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.