Do it like Super Meat Boy. I assume your game has levels of some sort since its a puzzle plat-former, so as you mentioned Super Meat Boy I believed it's a great example for your question.
In super meat boy, the way you control meat boy stays the same throughout the game, it's only the mechanics of the levels/environments that change. Therefore every mechanic the player needs to know is introduced in the first few levels. Please note these are not "tutorial levels," they take the same form as every other level in the game although they teach the player something new they are not presented as tutorial levels.
Basically, in Super Meat Boy the game gives the player a situation where there is only one solution and that solution involves some new skill that the player needs to be taught. Because as humans when we see a problem and can't solve it we will attempt to do something we haven't tried before. An example of this is when Super Meat Boy introduces the ability to jump up walls, the game gives the player a tall wall where there is no other way passed this obstacle except jumping up the wall (this is obviously a reference to Indie Game: The Movie). As a human, you will try to see if it possible to jump consecutively up the wall and get to the top. Instead of just telling the player in some obscure dialogue box you can jump up walls that the player might ignore.
This Super Meat Boy method is great, since, like you said, the player receives satisfaction from learning the new skill on there own rather than being told. It's also much easier for the player to remember this newly discovered skill because they had to think about it, whereas most people will just skip passed the text and just completely forget, and therefore may end up getting frustrated on a later level (usually blaming the developer for not telling them what to do).
EDIT: Like DinoDev82 said, "Don't just do it like Super Meat Boy".
Here I just wanted to give an example and since you liked Super Meat Boy and it's method I felt it necessary to explain what that method is and how its works.
Spoiler Warning: there some slight spoilers from braid that follow (nothing plot related)
Another example you can look at is Braid, being a puzzle plat-former I feel it is also quite relevant. If you have ever played braid you'll notice it also teaches the player new skills through its level design rather than providing tutorials and text.
I particularly like the introduction of the green glow mechanics (I don't really have a decent way to describe it) as it is an example of what Stéphane Bura said about exploring a combination of skills and exploring the complexity of a skill.
The picture above is the level where the player is first introduced to the real time green entities that don't reverse when the player reverses time.
By this time in the game the player has learnt about the Monstars and how to kill them, what a key is and what it does, how to reverse time etc. So since the player has learnt all of this previously the game can freely build on those mechanics or in this case alter them. The player knows that they need the key to unlock the door and continue. So they jump in the pit after the key (some people will do this without hesitation). Now the player realizes that they are stuck, however the player knows that there is one way out, reversing time, so that's what they do expecting the key to stay down in the pit, but it doesn't. Almost unknowing the player connects the dots and they now know green entities or objects are different and don't follow the reversal of time mechanics.