The best way to level up quickly is to complete all quests (story and side) and to work on challenges -  simply killing a few enemies with all the different weapons classes will get you 5000 exp(12 Days of Pandora). this is just an example. the challenge list can be accessed from the Echo Log screen.

Power leveling: If you have a high level character that has completed the first playthrough you can use Borderlands exp sharing to level up another character. Load a splitscreen game with your high level character as the first player, select a new character for the second player. Load the game and warp to the Trash Coast. Leave player 2 at the New-U Station, and take player 1 and kill the Rakk Hive. With a 51+ level character the Rakk Hive will be a level 51. The exp gained will be tiny for the high level but huge for the level 1, and with the right weapon it only takes about 2 minutes to kill the Rakk Hive.