Mining serves three professions: Blacksmithing, Engineering and Jewelcrafting, so it's really good combined with any of these.
Learning Outland Mining
Go to Outland and find Hurnak Grimmord (Alliance) at Honor Hold, or Krugosh (Horde) at Thrallmar in Hellfire Peninsula, then learn Outland Mining. You can also learn it from Hanlir at Shattrat City. (or from Fono, if Hanlir is hostile to you)
1 - 75
You can level from 1 to 75 in both of these zones below. Fel Iron will stop giving skill points at around 40, so you will only gain skill point from mining Adamantite Ore after that.
I marked a few caves with a red X on the map. You can usually find one or two Adamantite Deposits in those caves so you should go inside them.
Netherstorm is also an excellent place to level Mining. Just like in Nagrand, I marked two caves with a red X on the map.