Darth basically covered most of the big ones, but I'm surprised he never mentioned the Lucky Egg.
I don't know which game you're playing, but it's best to get a Lucky Egg for training. To get one, you have to catch a Chansey. There is only a 5% chance that this caught Chansey will have one of these items, so my recommendation is to bring along a Pokemon with Covet, like Linoone or Skitty.
Anyway, once you've got one, you give it to a Pokemon as a hold item, and gives you a 1.5x boost in the experience you get.
My final recommendation that hasn't already been mentioned is to look for Pokemon with either high bulk or high Base Stat total. Bulky and strong Pokemon, of course, give much more EXP than the average Pokemon (And speaking of which, Chansey can give about 700 EXP at only Lv. 15, and that's if it's found in the Wild).