When I wash bottles, I throw about a dozen bottles in a sink full of hot water and Oxy Clean Free (PBW works too but Oxy Clean is cheaper). Make sure to fill the bottles with the solution too, to soak all the beer residue out. After 10-15 minutes you can easily peel the labels off (with most brands). Occasionally you have to scrape the label off with a butter knife or spoon. With some brands that's not enough and the label is really stubborn - I have enough bottles that I just recycle those ones. After a total of a half hour or an hour of soaking, I use a green Scotch Brite to scrub off any remaining label material or glue. Pour out about half of the Oxy Clean and give it a good shake, then dump. Fill it halfway again, shake, dump. Then give em a good thorough rinse and stick another dozen bottles in the sink. I've never used a bottle brush.
As the Oxy Clean solution cools down, it takes slightly longer to soak off the labels and beer residue, but not much. You can either keep using it cold, or ladle half of it into a pot, bring it almost to a boil, and mix it back with the cold stuff. One sink full of solution will easily clean several cases of bottles if you have a backlog. Sometimes I'll just leave it in the sink for a day or 2 and slowly pick away at 3-4 cases of bottles.