The best way to find all the Shamans, and for that matter the Idols and Explorers, is to explore all around every level when you get there. These things tend to be tucked in out-of-the-way places. If there's a stinky plant, or a wall requiring TNT, or a wall requiring Pickaxes to climb that appears to serve no function on the main quest, then there's a pretty good chance you'll find something useful if you explore that area (even if it means having to come back in the future). Look under ramps, atop ledges, behind moving walls, stuff like that. A general rule of thumb is that there are very few things in this game that are not there for a reason—if you see some boxes that let you climb up to another area, for example, there's probably a reason why you should climb up there.
The easiest way to confirm whether you've gotten all the Idols, Explorers, and Shamans is to buy the "notes" from the Shaman (Cavern Notes, Jungle Notes, etc.). These tell you, for each level: "Idols x/y," "Explorers x/y," and "Shaman." "X/Y" denotes "you've found X, there are Y total on this level." For "Shaman" it says either "Waiting" (i.e., you haven't found him yet) or "Gone Away" (i.e., you found him and bought something from him).
The Smash Strike and the Breakdance Strike are more useful in the scheme of things than the "notes," so I suggest buying those in the near future if you can. The Breakdance Strike in particular is useful in the mountains and the Smash Strike is useful in the caverns, although you can get past either area without these abilities.