Now your task is simply to try and track down Sephiroth. First, you should go rest in the house that you rested in before. Then, go to the north west. Pick up the Viper Halberd and jump up the spike stairway on the tall shell. You'll have to kind of wiggle around a little up on top to figure out how to get to the passage leading west. When you do get there, you'll be faced with a large cave with a whole bunch of vertical passages you can go up and down. This little maze isn't too hard to figure out with a little doubling-back and so forth. When you get to the far left passage (it kind of looks like a big ladder or trench), go down first. Yes, it looks like there's nothing down there, but if you check it out, you'll find the Magic Plus materia hidden down behind the rocks. Now go up and right, then up, and you'll find yourself in an icy, frozen, wasteland.
Make your way around the mountains and northeast to Icicle Village, a small town with some important clues about what has happened in the past. First, buy yourself some new weapons, since those weaker double-AP weapons you may have been using up until now won't really cut it anymore. Also stock up on any healing supplies you need, then explore. There's an X-Potion on the top floor of the inn, and the upper left house contains some interesting and tantalizing storyline information. Don't forget to watch all the videos.
When you're pretty much finished here, go talk to the guy wandering around in the back of the screen. You can chat with him and let him be nice to you, but in order to move the story along, you'll have to try and ignore his warnings. At that point, Shinra will show up, led by none other than Elena the Turk. It's simple to dodge her wussy punch and watch her roll out of town. However, Icicle Village is Shinra territory now, so you better find a way out of here soon. Go talk to the kid with the snowboard He'll let you borrow it, since he's not going to be using it for a while. Make sure you get the map out of the house just to the right of the kid's before you leave. Then head for the slopes, strap on your snowboard, and get set for a fun little mini-game. Don't worry about doing well--save that for the Gold Saucer. For now, just have fun.