There are two problems associated with skill increases through training: finding a trainer and paying for the training.
Finding a trainer is the biggest headache of all. The solution is simply to go everywhere and talk to everyone. When you find someone with "Training" in their dialogue options, click on it to see which skills they train. If it's something that you may need now or in the future, make a note of their name and location.
Although you can train skills all of the way up to 100, there is only one NPC for each skill who can do that. Most trainers are going to stop somewhere around 50% or 60%. Additionally, you cannot train a skill higher than its governing attribute. So if your Strength is at 54%, you can only train your Long Blade skill to 54%. Magical enhancements to your attributes will allow you to get past this barrier, so invest in a few potions or spells if you're intent on training to very high levels in a skill.
UPDATE (August 2010): if you are affected by a "Drain Skill" effect and get a skill increase during the time that the effect is active, you will keep the skill increase when the spell wears off. For example, if your Destruction skill is drained down to 40 and you manage to get off enough Fireballs to bump it up to 41 before the spell wears off, then you'll keep that point when the spell's duration expires. Which then leads to the possibility of casting a "Drain" effect on yourself to bring the skill within the trainer's abilities and then keeping the benefit of the training when it wears off. Which leads to a similar idea with a "Damage Skill" effect. The advantage being that the effect lasts until it's restored through spells, potions or shrines (another reason to keep those Almsivi Intervention scrolls handy).
Money is tight in Morrowind. There are only a few merchants who have more than a couple of thousand gold for barter and most have less than 1000. This means either traveling around to multiple merchants to unload your goodies or making a plug-in that gives merchants more money to barter with.
The reasoning behind this is fairly sound from a developer's standpoint. If you can train your skills any time you want, what's the point in raising them through use? So, annoying as it may be, doing a lot of running around is just the way it was designed. I'll admit that my annoyance stems from impatience and greed more than anything else, so I just grit my teeth, live with it and cry a lot when I can't get a decent price for a really neat weapon that I don't need because the merchant doesn't have enough to pay for it.
You can make your training experience a whole lot cheaper by improving the disposition of the trainer as much as possible. Generally speaking, most NPCs who offer services need a minimum disposition of 30 before they will even offer the service, but that is not a hard and fast rule in my experience.
If the NPCs disposition is low, the service costs more. If it's high, it costs less. Here are some numbers that I generated with a character trying to train a skill that was at 20% (I wasn't paying attention to Personality or Mercantile skill levels, which also affect the final price):
The higher the trainer's disposition, the cheaper your training will be.
So if you're going to spend some gold on training, you'd be well advised to spend a little of it on sweetening the trainer's disposition. Spending a few 10 gold piece or a couple of 100 gold piece bribes to get the disposition up to 100 could just about double the number of training sessions you could afford. You will more than make up for the bribes by the additional training you can get. And the increased disposition lasts for a long time, so you can enjoy the benefits multiple times.