http://www.youtube.com/watch?v=K8UDQIfKdBo
Sorry about the sound. I have no idea why it gets like that when recording melee.
Against sheik what should I do? Any other general tips would be great as well.
I think you need to be faster, and more decisive. You would float really close for a while, but not do anything. And you're too close to Sheik to just float, and then not do anything right out of it. Branching off of that, make sure that your moves hit, or that you can act out of a whiffed move (in order to bait a reaction, or retreat). You seem to get punished for throwing out moves that are too obvious/obviously won't hit.
Edge guarding Sheik is really tricky. If you can, try to go out to them, and bair/fair/nair their second jump (only do this if you are certain you'll hit it, otherwise you've just put yourself in a bad position). If not, you can throw turnips out at them, to eat their second jump, or just wait by the ledge and react. Once you've taken their double jump, GRAB THE LEDGE. I can't stress enough how dead Sheik is when she is forced to up-B. The worst case scenario is that Sheik lands on a platform, or really close to the center of the stage, and you should still be able to roll/getup off the ledge (below 100%, but if you know they'll go for the stage, you can time it when your over 100% fairly easily) and punish them. Downsmash/reverse FC nair are probably the best options for punishing the up-B lag.
Sheik on the ledge: At low percents, you can afford to get closer to the ledge, bait an attack from it, and CC > punish. At higher percents, you should try staying further away from the ledge, in a float height just underneath a platform, from which you can react to most of Shiek's options. If they love jumping from the ledge with or without an attack, a weak dash attack (with the tips of her fingers) works well, too. I noticed that you seem to stand too far away from the ledge to effectively punish Sheik with more than a turnip. I recommend being right underneath the center of a BF/YS/DL platform (1/4 stage length away from the ledge on FD).
Getting under her is very good, which you should try to do as much as possible, with dash attack, down tilt, low FC uairs. Even if you don't get a combo, you've stopped her momentum, which is still really good. Try to look for her jumping habits (Sheik's seem to like jumping), and see when you can get aerials under her.
I think you float too low, because you get dash attacked out of it. But you may just need to float more safely.
Well, this is more or less what I thought of. I hope this helps!
EDIT: Sheik's shield is really, really, really stupid. Unless it's really low, just grab her, and throw her offstage (or downthrow, if you're unsure).
I've been taking a look at a lot of Peach/Sheik videos from various players just to see how they do it. Certain styles of Sheik don't seem to be as much of a problem to me. The big problem for me in terms of style would be something similar to the way Amsah plays that MU, at least in NTSC. 
