Take the train to Makhinjauri (also transcribed Makhindjauri) - that's the closest passenger station to Batumi. (Though you can just as well ask for a ticket to Batumi.)
There's currently one night train every day, which departs Tbilisi at 22.45 and arrives at 7.25 (the one from Batumi to Tbilisi leaves at 22:25). So the travel time is 8h 40min. The train makes lots of stops all night long (like ~20).
There's also one daytime train (each way) daily, which is a lot faster, 5h 15min. (It leaves at 8.30 from Tbilisi and at 17.55 from Batumi, if I read the railway.ge schedule correctly; I haven't tried this train myself.)
First class (sleeper) ticket in the night train costs 40 GEL (20 €); you'll share a cabin with one other passenger. (Second class is just 23 GEL, but I don't know what that's like.) Buying the ticket early may be a good idea to secure a sleeper. Make sure to have your passport with you!
Tbilisi station is easily reachable by metro (Station Square aka Sadguris Moedani aka Vagzlis Moedani) or taxi. Do reserve some extra time, however, if you don't know the station beforehand; it's not huge, but the platforms aren't marked very clearly.
The Makhinjauri station is some 5 km north from central Batumi, but it's easy to continue to that direction once the train arrives. A bus cost me 1 GEL (I took #10 which goes through Batumi centre but doesn't terminate there), and a taxi could be around 10 GEL depending on your haggling etc. There will be taxi drivers offering their services right when you get off the train.
The 1st class sleeper is not that comfortable (I'd say it's good Soviet Union level), but most likely you'll get some sleep. (Though according to the Georgian businessman I shared the cabin with, "there's no comfort in our trains" and he never sleeps well there.) Earplugs are a must to provide partial relief from 1) noise the train makes (sometimes really loud) 2) laughter, TV or general rowdiness in the car 3) your cabin partner's possible snoring.

1st class sleeping berth. Photo by me, May 2012.
As for safety, it generally seemed safe to me, though I guess how safe you feel depends on who you happen to share the small cabin with. There's a conductor / guard in every wagon (who, according to Wikitravel, "protects the passengers from drunks"). In my case she was friendly and had good attitude (though I'm not sure if she did much about the noise some passengers made after midnight). NB: the Wikitravel article suggests female solo travellers should consider booking both berths of a 1st class cabin, just in case.
So, this can be a cool experience especially if you like trains, but the bus/minibus option definitely has its strong points too (it's cheaper and takes just 4-6h (?), with many more daily departures, and nice views daytime, I've heard).
Tbilisi-Makhinjauri night train ticket. Photo by me.