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. With the introduction of the Burning Crusade expansion, the game has introduced a number of staves with stats befitting melee classes; many staves have been appearing that are designed for feral-specced Druids, with melee stats and enormous bonuses to Feral attack power. The only classes not able to wield staves are Paladins, Death Knights, 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 . 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 , or , that is obtained from quest chain from Ghostlands. 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 from Arcanist Doan.