When a character gains enough Experience Points to rise in Level, he or she also gets a number of Skill Points (and possibly Feats).
Skill points and Feats must be defined when they're received; they cannot be saved up for later use.
If the character simply wishes to improve a Skill or Feat they already posess (e.g., to take Great Cleave when they already have Cleave, or to go from 4 skill ranks in Listen to 5 ranks), then no additional training is required. The character is assumed to have done enough "on-the-job" training to be able to use the new Feat or skill level.
Note: In some circumstances, I may be tempted to rule that you haven't used the Skill enough to be able to improve it without training. It would be a good idea to keep some sort of record of how often you've used your skills successfully, perhaps by placing a tick next to the Skill Name whenever you succeed in using it. If you have 5 ticks next to a Skill, you will probably have done enough to qualify for training-free improvement.
If the Skill or Feat isn't a direct improvement on one already posessed by the character, then s/he gets no benefit from it until such time as s/he has received some training in it from some skilled practitioner. In order to provide effective training in a Skill, the teacher must fulfill at least one of the following criteria:
An untrained teacher can train somebody up to half their own Skill Ranks only (not including Ability modifiers or any other modifiers).
A trained teacher can teach a Skill up to their own Skill Rank minus 2.
Example: Spork the Unwashed, a 4th-Level Rogue, wishes to learn how to forge documents. His brainy pal, Hoek the Sanitary, has 6 ranks in the skill and an INT modifier of +4. He can teach Spork up to 3 ranks in Forgery (½ his own skill rank of 6).
Example: Spork wants to be a better forger than that, so instead he goes to see Bjönk the Unscrupulous, Professor of Forgery at the Clearwater Academy of Naughtiness. Bjönk also has 6 ranks in the skill, but because he has a Profession as a Teacher, he can teach Spork up to 4 ranks in Forgery (His own 6 ranks, minus 2).
As a general guide, assume it will take (6 - Ability Modifier) months to gain one Skill Rank in a new skill. This assumes relatively uninterrupted study — at least four hours a day, at least five days in every week. If training is erratic, then it will take longer to achieve the new skill level.
The cost to train in a new skill varies depending on the rarity (or legality) of the desired skill, and of course, on the skill level and fame of the teacher.
The costs for maintenance training are subsumed under general living expenses when the characters are between adventures. Fighters will have to spar with their peers, wizards will have to study, thieves will have to, well, thieve. If characters are unable (or unwilling) to fork out for general training costs, they will start getting rusty, and will start receiving penalties when they do try to use the skills.