A trainer is a special type of NPC that gives out classabilities and spells, or professionskills and recipes. Most of these improvements cost money (increasing with level) and only become available at certain levels. Guards in capitals can point players to the nearest trainer.
Players looking to increase their skill in a profession need to find a skilled trainer to help out.
Before Patch 2.3, Master was a title given to a trainer who could train a character to the Artisan stage of a profession. After Patch 2.3, most Master titles were removed from trainers, and all capital city trainers could train up to Artisan.
In the past, Master Trainers would be found in various far-flung locations for each faction. Some were even found inside dungeon instances!
Other titles
Previous to Patch 2.3, profession trainers used to also have various levels of trainer titles from Journeyman to Expert to Artisan, such that they could only train to below the level of their title. Now in Azeroth (except Northrend), there is a main trainer and an occasional apprentice trainer (mostly in Silvermoon City and Undercity for some reason).
Patch changes
Patch 4.1.0 (26-Apr-2011): All major cities will now have every type of profession trainer and their associated trade supply vendors.
/Patch 3.0.2 (14-Oct-2008): Demons now learn skills as the character Levels. Existing Trainers/Grimoire sellers were either removed or turned into redundant NPCs.
Patch 2.3.0 (13-Nov-2007): The capital cities now possess Artisan level trainers for the primary professions they support, and are surrounded by their newly-dubbed Apprentices where applicable.