Cheapest travel
Michael Borgwardt is right about the cheapest alternative: a combination of early-booked trains, buses, rental cars would be the cheapest. If you want to see the northern lights, you need to go the far north, best is north of the Arctic Circle. The Aurora Sky Station in Abisko is very good for aurora watching, as it's right in the auroral arch and has the most clear skies of any place easily reachable in the region.
Clothing
About clothing and footwear: remember that Scandinavia is big. From the North Cape in the north to Malmö in the south is roughly 2500 km, as far as from Malmö to Sicily in southern Italy! In the north, where the northern lights are (you're unlikely to see them in Oslo/Stockholm/St Petersburg), October can see temperatures below -15°C with 20+ cm of snow (e.g. in Kiruna). The south has an entirely different climate.
Road conditions late October / early November in the far north
If you go later, in late October and early November, you need to be wary of road conditions. Southern Scandinavia (south of Stockholm/Oslo/Bergen) may be fine, but in the far north, it can be extremely icy around this time of the year. Temperatures may hover on both sides of 0°C, which make conditions worse than mid-winter, when temperatures are continuously below 0°C and roads are covered with packed snow.
Icy footpath near Kiruna, Sweden, 30 October 2011 (Midnattsolstigen)
If you are not experienced with driving in icy conditions and planning to go far enough north to see the aurora late October / early November, I do not recommend driving long distances, particularly not in the dark. Then it's really better to take public transportation between cities, and possibly rent a car to carefully get around locally.
On 4 November 2011, the town of Kiruna, Sweden turned into an open-air ice skating ring. Not that under normal circumstances, there would be 10–20 cm of snow.