Those of us here at Hostelz.com have done a lot of travelling and we have a lot of opinions about the best stuff to bring on a hostelling trip. There are a lot of books and websites with packing advice that all pretty much tell you the same things (wear comfortable shoes, don't forget your toothbrush, etc.). So we'll the most obvious stuff and tell you about a few things you maybe haven't thought of.
With eight people sleeping in your hostel dorm room, there's a pretty good chance one of them snores. So unless that one is you, you'll want earplugs, and preferably the kind with the little string attached so you don't lose them as easily (unfortunately we didn't have the extra $0.50 in our budget to get the string ones for the photo...). Although they don't have a string attached, many people swear by Hearos earplugs as the best earplugs to get because they're especially comfortable and do a great job of blocking out sound.
Once you get one of these for your keychain you'll wonder how you ever lived without it, whether your travelling or not. But they're especially handy for reading a map at night or digging through your backpack in a dark hostel room late at night (don't be ones of those people who turn the room lights on while people are sleeping to find a toothbrush). Get a keychain flashlight with a "white LED" bulb. They're tiny, bright, never burn out, and they're super efficient so the one tiny battery will last you almost forever. They're available in many stores, or you can also get one of these online.
You need to bring a towel because most hostels don't offer towels (and the ones that do usually charge a fee). But here's the thing, there's no need to carry a full size towel with you. All you need is a small hand towel. Just remember to shake off a little before you start towel drying and it'll work just fine. Or, if you prefer you can get an actual travel towel.
There's nothing worse than realizing you're on the right street, but you've been walking for the past 45 minutes in the wrong direction. Make your life easier and get a little keychain compass. It's nice to be able to get a sense of your orientation when you walk out of a subway station. Even if you don't know exactly where you are, at least you might know which direction to head. By the way, small compasses are convenient, but some of the really tiny ones don't work very well, so try before you buy.
Small Garbage Bag
If you wear your socks a couple days while you museum hop, then put them in your backpack after you change, pretty soon everything in your bag will smell like feet. So bring a small plastic garbage bag for your dirty laundry, or maybe even some large ziplock bags to be extra safe.
Hostels don't always offer lockers, but when they do, usually you have to provide your own lock, so bring one with you. But just as importantly, you need a lock that can fit through the holes in your backpack's zipper pulls so that you can lock your backpack. Why? Well it may not keep someone out of your pack for long, but it will discourage pickpockets from taking stuff out of the back of your pack while you're wearing it... which does happen (particularly frequently in Barcelona)! So if your big lock doesn't fit through your zipper pulls, then also get a smaller one that will. Combination locks are probably best since there's no key to lose. This one is one of our favorite locks.
Hostelling International Membership Card
Not all hostels belong to Hostelling International (HI), but a whole lot of them do, so you'll probably be staying in HI hostels during your trip. And a valid HI membership card is required to stay at HI hostels. Some HI hostels allow non-members, but an extra fee will apply. You can get a membership card before your trip here.
Years ago people staying in hostels were expected to bring their own bedsheet to sleep in. Today all hostels provide sheets, but a few hostels may still charge an extra fee for sheets. So even though it isn't necessary, some people still like to have their own nice sleepsheet to sleep in every night. (Sleeping bags are usually not allowed by the way.) So what's a sleepsheet? It's basically a regular bedsheet folded in half, and it's usually sewn part way up the side. You can make your own, or buy a nice silk one online.
ATM Card / VISA Checkcard
ATM machines are everywhere and they're a good way to get local currency without paying high exchange rates. Get a card that's also a VISA Checkcard so you can use it like a credit card (which is probably a better idea than using a regular credit card because most credit cards charge an extra fee for purchases in a foreign currency, but a checkcard usually doesn't). And if the magnetic strip is nearing the end of its life, get a new card before your trip. And one more thing, before your trip, memorize the credit card number and expiration date of one of your credit cards (preferably one that you're not taking with you). Even if everything you own is lost or stolen, there's a lot you can do with a memorized credit card number in your head, including making phone calls.
Some hostel showers have floors that are even dirtier than your feet. And even if they look clean, you still might end up getting athlete's foot. Get a cheap pair of light-weight flip-flop sandals and shower without worry.
Travel Tissue Packs
A valuable multi-use item that works well not just as facial tissue, but also comes in handy as a substitute for toilet paper, which can be a rare item in some areas, especially when you need it most.
Ok, this is something you could live without, but a small inflatable pillow takes up only a little room once it's deflated, and it's so nice on those long train and plane trips. And it's probably more comfortable than the lumps that pass for pillows in most hostels.
Convenient for sticky hands after eating, not to mention useful for before eating if you like to avoid getting sick. You can get generic wet wipes, or the original classic "Wet Ones".
Other suggestions from Hostelz.com readers: sleep mask, money belt, hand sanitizer, alarm clock (or a watch with an alarm), 2 photo copies of your passport and plane ticket (leave one copy with someone at home), "mole skin" or blister patches for your feet, important phone numbers (embassy, consulate, relatives at home and in the country visited, credit card companies, etc.), sun block, mosquito repelent, condoms, sewing kit, swiss army knife, matches, bottle opener, bandaides, a first aid kit, a sarong (multiple uses including a towel, blanket, bag, or clothing), sink stopper plug for washing clothes in a sink, string for hang drying clothes.
Wheeled luggage might seem like a good idea, until you find that you can't go more than 10 feet in most countries without hitting steps or some kind of bump that you have to lift it over. Not to mention that the people behind you are always tripping over it. You'll soon find it's more trouble than it's worth and you'd be better off with a backpack. The only possible exception might be for travel within the US, since the country's strict laws to help the disabled have made much of the country wheeled-luggage-accessible. If you can pack really light, our favorite backpack that's small enough to take on a place as a carry-on bag is the Jansport Odyssey Backpack. If you need a little more space, the Teton Sports Scout 3400 Internal Frame Backpack is our favorite all-purpose hostel travelling backpack.
Umm... bad idea.
The most important thing: DON'T OVER PACK. Almost every inexperienced traveler takes way too much stuff on their first big overseas trip. But almost no traveler complains later than they wish they had brought more stuff. You can buy almost anything you need in almost any country in the world if you realize later you needed something.
I've traveled overseas for 3 months with only a small backpack. I felt as free as a bird as I easily moved from place to place. I could even spend some time exploring a city without even needing to drop off my luggage at the hostel first. I've seen plenty of travellers in airports and train stations almost in tears because they're exhausted and stressed out over lugging a huge backpack or suitcase everywhere they go. Overpacking be the difference between a carefree vacation and a stressful nightmare.
Ideally, your backpack should just barely fit within the size limits for carry-on baggage on your flight (and it's great not to have to worry about your check-in luggage showing up!). And if you're travelling by train and your bag is small enough, you can stow it on the floor or above your seat rather than the luggage racks at the back of the train car where it can easily be stolen.
How is this possible to do? The is going to sound crazy to some of you, but for clothing this is all you need for even the longest overseas trip: three shirts, one pair of long pants ("slacks") or jeans, one pair of comfortable shoes, one pair of shorts (guys can use them as swimtrunks too, girls should also bring a bathing suit if needed), a few pairs of socks, a few pairs of underwear (and for the girls, one bra if needed), and a light sweatshirt or jacket (depending on the climate). That's it! Seriously! Everything should be dark colored everything should go with everything else. You can wear each thing at least a couple days (everyone does while backpacking, it's ok), and then you wash your clothes about once a week (wear the shorts while doing the wash). Lots of backpackers have done it this way, and you can too. If you decide later you can't live without some extra clothing, you can always buy something during your trip.