Pick your music first, with no particular reference to the dancing. 4/4 with a strong beat is easy. You can cut any video to go with any music. Don't change the speed of the music.
Easiest way to do it is to use an editor with a waveform view. For your first one it doesn't much matter what you use - Windows Movie Maker, Sony Vegas, iMovie... TBH I have never used these as it's a lot easier in a real NLE like FCP7 or Adobe Premiere but obviously these are overkill for your porpoises.
Look for the big wibbles in the waveform and set markers there. Put all your clips in your source bin. Drag a video from your source bin into the viewer, hit I to set the In point, scrub forward a bit and hit O to set an out point. Pull this video down onto your timeline (just drag it on) and with a razor tool cut it to fit to two markers. (There are lots of ways to do this, google "three point editing")
Build up your timeline until it is full. If you want to make the video run faster google "speed up + name of your editing app" or "time remap + name" or "ramp speed + name" - this is how to find out how to do anything. If you want to do a short tutorial then there are plenty of beginners tutorials available free for every editor except possibly Avid MC.
Making it look great: Try to match motion across shots. If you have any impacts on the video like a "hand hit" or "leg kick" line them up with drum beats. Go for a big finish with increased speed video and shorter cuts.