Motion tracking in very shaky footage?
If you have access to adobe premiere pro CS6+ or after effects CS5.5+.

Try using the warp stabilizer effect and see how well it handles it.
It would automatically attempt to stabilize the footage (and rolling shutter).
This is probably the easiest thing to try first before doing manual frame by frame tracking.

You can see a video by adobe giving a quick overview of it here:

http://tv.adobe.com/embed/902/12454/