I am planning to do a backpacking tour to the mentioned countries. I will start from Warsaw, and since my final destionation is Kraków, I want to go to TAL from Warsaw, and then go south, visiting Estonia, Latvia, Lithuania and Poland.

First, which cities do you recommend in the Baltics(of course I will visit the capitals, but I want to experience the countryside too)?

And what is the easiest way to get from Warsaw to Tallinn? Are there any railways, or only buses?

I don't think there's reasonable, if any, train service on that route. Bus is an option, but flying might be the cheapest, and certainly the fastest. Train is going to be a problem going south from there as well...

Well... as I have just ascertained from www.bahn.de, you CAN get to Tallinn by train from Warsaw... but you have to go via Belarus or Russia, both of which require visas.

You can get from Warsaw to Vilnius by train without crossing into Belarus (once a day). I've done it, and it's quite a pleasant trip on the Polish side but slighly less so on the Lithuanian side as seats on the train are rather uncomfortable (or at least they were 18 months ago).

You can also get from Vilnius to Riga - though it involves a rather-too-short overnight stop on the border (arrive 2200, depart 0440). This is a trip I have not done.

As for other places to visit... we spent a few days in Klaipeda in Northern Lithuania (very comfortable train ride from Vilnius!), and although the town itself is not particularly special we really liked the area around it. We rented a car and took day trips along both sides of the Curonian Lagoon and also into Latvia.

Of the three Baltic capitals Tallinn is probably the prettiest... but it's also the most touristy.

For transportation between the Baltic capitals, I would definitely recommend the busses. They are comfortable, the schedules are packed, and dirt cheap.

A month ago I took luxexpress (www.luxexpress.eu) between Tallinn and Riga, and Riga and Vilnius. The drive is 4 hours, but the busses have a "business lounge", a separated compartment at the end of the bus, where 4 people sitting share a table, there's a 220V power socket and WiFi coverage. There, you also get a bottle of water and a bag of nuts to munch on. Both business and "economy" parts of the bus can use a coffee machine onboard free of charge. The rides in the business lounge cost me 22 and 17 euros, respectively. As I said... for 4 hours' drive each. Amazing Tickets can be purchased online, you just print out your boarding pass and bring it onboard.

They also have a bus route from Warsaw, but that's just too long a journey to endure on a bus... If I were you, I would fly into VNO from WAW, then take the bus up north... or maybe fly into TLL initially, then go down south to Vilnius, from VNO to WAW by train, and then to KRK...

Well, that's true but I didn't consider going to Moscow or Minsk a reasonable route Both require visas and both are pretty significantly out of the way (Moscow more so).

And actually, wouldn't it require both visas? I don't think there is rail service from Belarus to Estonia without going through Russia, right?

Keeping in mind that my trip was in 2005, I wouls have to agree that Tallin was the pick of the capitals. We used bus most of the time.
A suggestion for outside the capitals- I suggest that Tartu in Estonia is certainly worth a couple of days.
Keep in mind that some areas seem to be pretty seasonal. Our trip in late Sept meant that some spots were in shut down mode eg Curonian Spit. I also remember having to help push start the bus when we were leaving.

I'm not sure if this pertains to my reply or not, but source of Moscow-ish confusion could be that VNO = Vilnius, and not Vnukovo (VKO)

A couple of thoughts.

1. I took the infamous Vilnius-Warsaw overnight bus, and managed to survive.
The train does not run daily, so watch your schedules or you'll end up on the bus. If you can find a low cost carrier that flies to the Baltics, I would most strongly recommend it. Consider flying to Estonia or Finland, and working your way south. That would also give you an opportunity to check out Helsinki.

The hydrofoils in Tallinn have deals where you can day-trip to Helsinki if you like.

2. Check out the islands off the coast of Estonia. Saaremaa and Hiiumaa are the most famous.

3. Bialowieza National Park in Poland is roughly where Poland, Belarus, and Lithuanian come together. It was one of the highlights of my trip to the Baltics/Poland. I've read it's what most of Europe looked like prior to the Industrial Revolution in the 18th Century.

The train DOES run daily - I have just checked.

Depart Warszawa Centralna 0735, arrive Vilnius 1753, seven days a week.

Thankyou very much for the answers!
After considering various choices, I think the best solution is a flight from home to Helsinki, and then continuing the trip to the south. I have a few books and brochures, but I'm interested in personal experiences, what is recommended to visit in Estonia, Latvia, Lithuania, Poland.

I am planning to visit the capitals, some cities of Poland, Kaunas, maybe Turku in Finland and the Bialowieza National Park. But I do not really know what worths visiting in the countryside of the three Baltic countries.
What do you recommend?

If you are travelling in the summer you should consider Baltic seacost - from Riga to Jurmala (maybe even via Ventspils) to Liepaja-Palanga-Klaipeda-Curonian spit.

Other option would be to include Hill of Crosses

Trakai and its castle is a nice and eady daytrip from Vilnius

Another vote for the buses.

Doing the buses next month when I do Tallinn, Riga then Vilnius. Flying into Tallinn and out of Vilnius from Amsterdam. Could have added Minsk to the trip as well with the bus, but didn't want to bother with the visa.

You can take direct fligh to/from Tallin to Warsaw - it's quite cheap with LOT Polish Airlines.
It depends what would you like to see: if you are looking for cities I would recommend (in Poland) Krakow (with Auschwitz concentration camp and Wieliczka or Bochnia solt mine as a must - both Auschwitz and mines might be reached from Krakow by local trains/buses) and Gdansk. If you would like to start from Helsinki you can take a ferry or a plane to Gdansk (very nice 1000 years old city with plenty of historical places where the II world war starter and Solidarity movement + nice Baltic sea + one day in Sopot spa which is in the same city area as Gdansk), then a flight (faster) or train (slower due to rebuilt before Euro 2012) to Warsaw and then flight/train to Krakow

I truly loved Gdansk...not quite in the same league as Krakow, but absolutely worth a visit.