for Horde, I believe you talk to someone in the Rogue's quarter in UC. He sends you to the Barrens by the SludgeFen Farm to steal something from the top of the tower. Can't remember the name of the quest, but after that, you get Poisons lvl1. After that, any rogue trainer can teach you how to craft poisons.
You get new poisons basically every two levels. (ex. lvl22, lvl24, etc). Also, your maximum level is based on your actual level, so every time you increase a level, your poison level maximum increases by 5, must like your lockpicking, except keeping your poison level up is much easier. Poison supplies are easily available, especially in major cities.