How should the characters learn new skills?

I'm seriously stuck on how to make my characters learn new skills. I've been trying out many different ways but I'm not sure which one I'm happy with in the end. So I'm asking for everyones input in the hopes it may help me make up my mind!

At the moment I have temp skills attached to equipment, for permanent skills should I...

1. Just learn them by leveling.

2. Finding skill books while you explore. So once you read it a certain character will learn a certain skill. (I'm leaning more towards this one)

3. Buying skills fro shops.

4. Gain AP in battle and use that to learn new skills.

5. Just get rid of the temp skills and learn all skills permanently from equipment?

It really depends on what makes the most sense in your game world. If it's a futuristic rpg then maybe skills are downloads into the brain so they can be purchased.
Maybe they are special demons or spirits so they must be captured.
Maybe they are magical songs or rituals so they would be in books.
Maybe they are prayers so they are learned automatically on level up.
If your special equipment is magical maybe it grants the skills.
And you can use as many different techniques as you want. Pick what works best in your game world and story.

For example:  My games have had several distinct methods of learning skills:

1. Bards play magical music, so they need songbooks (bought or found) to learn new songs (i.e. skills).  I often have Bards learn a few basic Songs on their own so they get some automatic leveling up benefit.

2. Shamans learn to control elemental forces when the party experiences them.  So they learn skills relevant to what elements hit the party (i.e. enough Fire attacks teach the Shaman to do Fire attacks or protection)

3. Martial Artists are big into self-improvement, so they automatically learn combat Skills as they advance.  If I wanted to, I could easily have Masters who teach very advanced Skills if the party does quests, or Secret Techniques ---- books which teach powerful Martial Artist skills.

4. Mages --- learn Spells on their own as they go up in level, but the most powerful spells are bound to ancient wands the party must find, granting temporary skills.

So, look at your own game world and story and see what methods flow from them.  And consider game balance --- it's fair and reasonable to force the party to do difficult side quests or find rare artifacts to use the most powerful abilities.  But it would be rather annoying to force them to do this for the most basic Skills.

Yeah, this is a decision that is tied to your game world itself. Without proper knowledge about your game, we might be giving something that doesn't make sense in your game. Remember, don't add a feature just for the sake of adding it.

It's based off a D&D campaign I played. So it's a fantasy medieval type world. There are four characters. A Mage, A barbarian, A battle cleric and a ranger/druid.

So I guess it would make more sense for the mage to learn new spells from spell tomes, but I'm not too sure about the others. I wanted to avoid having too many features and making it confusing for the player.

probably try to just stick with how D&D based games handled it?

Well you had a choice of skills when you leveled up, but could only choose one. Though you could swap it round at certain levels. I guess the best way to achieve that would be common events? Course that would mean I'd have to create a lot of common events, then again the skill tomes would also require a lot.

Skill Tomes wouldn't require any Common Events, if by a Skill Tome you mean "Book which teaches one particular Skill." 

To create these Tomes:  on the "Other" tab for Items, there is a "Learn Skill" selection.  If you click on the "Effects" box, then double-click, you can select the "Other" tab from there.

As for other characters, you're building the game world, so you have the power to make decisions that are easier for you to implement, like "Character Class X only learns Skills from a Master"  and then modify the game world to justify the decision.    The easiest means, by far, is just to have the main Skill list learned automatically as the player goes up in level.

I do this a lot when building the concepts of the world --- I have a world idea  and find I want the game to play out differently, so I modify the game world to justify the new way it plays out.

You can restrict the skill use by making MP costs high or by using a Cooldown script so if you use one power, it blocks the other for awhile.  I do this with some Martial Artist skills.

But, I'm pretty sure I saw a D&D thread where interested game developers were creating an implementation of the D&D ruleset in RPG Maker.  You might want to take a peek at that thread, if you're looking for a D&D style game.