A staff is a two-handed blunt weapon, usually in the form of a long pole a bit taller than a person. They can be made of metal or wood. Some staves have small balls or other ornamental shapes on one end. However, these shaped ends are mainly decorative, and are not as large, sharp, or significant as they would be on a mace or polearm.
Staves are often the preferred weapons of casters. This is because they often have large Intellect stats or provide bonuses that boost casting spells. The only classes not able to wield staves are Paladins, and Rogues.
The list of trainers can be found here: Weapons trainers.
For Alliance casters, the first great staff to be found is in the Deadmines, the Emberstone Staff. If this is not obtainable, the quest reward is an acceptable substitute. For Horde casters, the first great staff found is a quest reward for doing Wailing Caverns, the . Both of these are rewards from a long quest chain you solo before entering the respective dungeons. Characters high enough to go to the Scarlet Monastery should run the library to get the Illusionary Rod from Arcanist Doan.