I hear that they have a Mining Trainer in the Undercity.  All you have to do to get there is head south out of town and go to the back of the Ruins of Lordaeron.  Then take the elevator down into the Undercity itself and ask an Undercity Guardian for further directions.