Fancy yourself a chef?  Head to the Undercity south of town for your training.  You can catch the elevators heading down at the back of the Ruins of Lordaeron.  Talk to one of those lumbering Undercity Guardians for further assistance once you arrive.