I deal with stealthed minions in one of 3 ways.
Area of effect
Flamestrike, holy nova, fan of knives, doomsayer, etc. can all damage stealth minions, however, the damage they do is not always enough. Mass silence can also help.
Random target spells
Spells that have a random target, such as deadly shot for the hunter deal have a chance to deal with a stealth minion quite nicely. The less minions the enemy has on the board the better (usually).
Taunts will force the stealth creature to attack it instead of something you want to stay alive. The opposing player could quite easily get rid of your taunt, though, and it doesn't work against minions, who are not made to attack, such as blood imps.