Pretty much everything that husband said, except don't roll when Sheik does her up-B. Just press up on the stick at the explosion part of her up-B, and smash/grab at lower damage, nail her with an up-B at higher damage.
The dash attack to fsmash is cool and all, but it only works at lower percent, and at lower percent what you need to be doing is racking up the damage, not smashing her. After a succesful dash attack, nail her with a tilt and combo that *****.
Don't spotdodge vs Sheik. It's too slow. She'll just nail you with a more powerful attack. Shield. Wavedash. Shield-wavedash. Jump from shield. Or just run away, but do not spotdodge unless you predict a dash attack or something like that which actualy has lag.
The general rule when recovering with Marth is FALL. Then come back up later. Use your floaty side-B first, and then jump later. Don't do either until you're out of needle range. Those needles with kill your momentum, and thus your recovery.
DI AWAY FROM SHEIK WHEN YOU GET HIT
When you get grabed ALWAYS DI behind her. All Sheik can do then is hit you with a BAir, which is not that bad considering the alternatives.
Marth's neutral A is very situational. If you need a quick attack, the side-B is faster.
Marth's counter is VERY situational and should not be used as often as you like to, especialy against a Sheik. It's fundamentaly flawed; if you can predict the blow, then you may as well just dodge it and land a more punishing move than the rather modest counter.
When your opponent has just finished the up-B or has broken his shield or you predicted his dodge or tech or he missed with a really slow move and you've got a guarunteed hit, do NOT fsmash. When he's right next to you, the fsmash is not very powerful. I know it's tempting, but you need to get into the habit of using Marth's up-B when you've got a guarunteed hit in close quarters (provided your opponent has some damage on him, otherwise he wont go far enough and he'll just nail you as you recover from ur up-B). The fsmash in general should be used wisely. It's more for edgeguarding and finishing combos. You suffer from what I like to call "Marthitis", or the excessive spamming of the fsmash. You gotta break outa that.
Mostly it looks like you just need good old match experience... and against people who don't suck. Those guys you were fighting sucked. You need tougher opponents to get better. My friend plays a mean Sheik, and I was forced to go over my Marth with a fine-toothed comb before I could beat him. Sheik is Marth's best training buddy. Sheik will force you out of the habit of just dodging around and fsmashing, and you have to be a good deal better than your opponent to win.