There is a regular bus service from Vilnius to Gdansk. I took it once, and from memory it was about 6 hours and runs daily. Like the Vilnius-Warsaw bus, it is an overnight one, and so not ideal. They tend to arrive very early in the morning (before 5am), so you almost need accommodation sorted for that night so you can go and crash as soon as you arrive. I also took the Warsaw-Tallinn bus, but never again. It broke down somewhere in Estonia, and all us passengers were just left to fend for ourselvers and find another way to get to Tallinn. You can find bus information on
www.eurolinespolska.plI am actually going to Vilnius and Minsk for the May long weekend. This time I am flying from Warsaw to Vilnius. It's not cheap with LOT, but preferable to spending a couple of nights on the bus.