Give detailed info about how something is used in the game via little mouse-over (or whatever) windows.
For example, let's say there is a random chance that there is a gating mechanic where you have to place these certain colored crystals on matching pedestals. Rather than communicating what the player is expected to do through some tutorial segment simply allow the player to hover the cursor over the crystal for a second to pop up a mouse-over window that explains that you need to place the crystal on its matching pedestal. If the player moves the mouse away the window disappears.
This way you are still giving the player a chance to discover and figure out things on their own but they can always get information on something in the game when they need it just by quickly checking out its data window. It's a fast an unobtrusive way to go about it.
one easy way to do it would be to have a totoreal message pop up everytime the player encounters a new mechanic
I personally loathe those, they are obnoxious and kind of break the flow of things especially when things are obvious enough that I can put things together myself. I like mouse-over windows (or otherwise manually popped up windows) because it is quick-accessed and for the most part stays out of the way unless you want it and gives you a chance to sort things out on your own.