I know you meant to say the Baltics, Mike!
Easiest way to get from Riga to Vilnius is by bus - Eurolines and Ecolines are both options, I believe. You can go to Kaunas also, but if you have time, Vilnius is beautiful - one of my favourite cities. There shouldn't be any border issues between Latvia and Lithuania. The Polish border with Lithuania was notorious, though I've heard recently that it is improving.
There are a couple of hostels in Vilnius, though we lived there so I've never checked them out. The one in Antakalnis is a bit out of the way - a hassle by bus as I recall. There's also one near the train station which is more convenient though in a run-down area. Not particularly unsafe, just dingy. Check out
www.inyourpocket.com for Vilnius accommodations options. We've had more experience with guest houses, which have been very comfy. There are amazing places to eat - try zeppelinai and the Tatar specialty kybynai, as well as saltabarsciai, a cold beetroot soup that looks like Pepto Bismal and tastes divine. Soups are a great, filling and cheap option in Lithuania. Delicious.
In Stockholm we stayed at the Af Chapman hostel, it was a great location, unbeatable price and the kids had a ball sleeping on the boat, even if we did hear ice smashing into the hull all night. You're sensibly not visiting in February, so hopefully you won't have that problem.
Enjoy, the Baltics are beautiful in September.