I made an armature and tried parenting it to the mesh with automatic weights. When I do so, the mesh moves almost completely off the blender world and becomes gigantic. Any idea why this could be happening? Below is a video of it occurring.
I suspect that either your mesh or your rig has been scaled up or down. In the transform area of the n-panel, Scale should be 1.0 for x, y, and z. If not (to quote the Mythbusters) there's your problem.
Do you know how to apply scale? If not, go to the Object menu at the bottom of the 3D View, select Apply > Scale.
If it's your rig that's been scaled, this may cause some weird behaviour even after you've fixed the scale (if memory serves). If so, I don't remember if there's a fix or not and you may have to rebuild your rig from scratch.
Hope it doesn't come to that.