In the past, I used to say "Herbs", then I was corrected and told that the "H" is muted and one should say "Erbs". Watching some video, the instructor keeps saying "Herbs". What is the right pronunciation?
The American pronuncation is usually /ərb/ without the h, while the British pronunciation is usually /hɜː(r)b/ with the h, but maybe without the r. It was formerly pronounced without the h in the U.K; the British author E. Nesbit used "an herb" in her book The Wonderful Garden (1911), probably indicating that she pronounced it without the h.
What is the right pronunciation?
That depends on which English, you speak. It is one of the many differences American English has from British forms of English. The h is not pronounced by Americans. It is pronounced by English (and other British) people. This page http://dictionary.cambridge.org/dictionary/british/herb?q=herb , demonstrates it.