What about hostels and bed&breakfast type things? Usually you can also get singles/doubles besides the 1000 a room dormitories in
hostels.
Euroline is sort of like the American Greyhound long distance bus thing.
Ofcourse there's
Ryanair for low budget flights (mostly to and from Britain), crappy service is included free of charge :-D. But there are probably dozens of low budget airlines in Europe these days.
