Well, when you say just started...they do not put profession trainers in the newbie zones. At least, I have not seen any.
You usually get the first group of them at the first city you are directed to after you leave your newbie zone. Your first city will be Anvilmar. I do not recall if there are herbalism or alchemy trainers there. You will want to check houses, towers and camps along the way as well. Often the profession trainers are removed a little from the city.
You can ask guards and they will direct you as well...and it may be that you will be sent to Ironforge. You may just want to cut to the chase and head there straightaway.
On the other hand...it would pay to dig around and find them local to Anvilmar since you will spend a few levels there before moving on...always nice to know where your closest trainers are.
Little story about that...I played an undead and did skinning/leatherwork...I went all the way to the Undercity to train and then to add recipes and train up...because I could not find trainers. Then one day i noticed a house set back near the water in Brill...off of the beaten path. Went in and there was a skinner and leatherworking trainer. I had spent so much time running to and from the Undercity and they were right under my nose all along. Now, when I move into a new city or zone and feel that I am going to be there a while for adventuring, I make an effort to find my class and profession trainers nearby.