www.wow-pro.com has good leveling guides, and there are others if you search the web. If you look, there are guides that tell you every quest/zone to do for every level from 1 to 60 to maximize your skill (one even tells you how much exp you need from the activities it describes).
The second time you level it will seem to go a lot quicker, just like the second time you travel somewhere. Took me six months to level first time, then only two months the second time.