This page has a lot of resources that should help you learn how to track motion in your scene.
However, if you're just starting out in After Effects, you should definitely start here. AE is not the kind of application you can just dive into without getting a good foundation in the basics. The link I gave you will take you through several good, free resources to get you started right.
You could also try using the warp stabilizer effect to stabilize your shaky ocean footage. Try these settings:
Also, have a look at this tutorial for more information on using the Warp Stabilizer effect:
I'm not trying to be anything but helpful so please don't take offence.
Step 1: Plan every aspect of your shot by deciding what you want to do and then list all the potential problems.
Step 2: Carefully design the production of the shot considering all solutions then decide on the simplest solutions for each problem.
Step 3: Carefully and skillfully shoot the elements and then conform them the production plan in step 2.
It sounds to me like you came across a shot of the ocean with and you'd like to add a moon to the shot. Even though you are kind of going about this backwards the same steps apply.
The same steps apply.
First step: The shot of the ocean is shaky, the camera isn't locked down. The shot of the moon is. So what is the easiest way to combine the two.
Second step: I can fix the problem by removing the camera motion from the shot of the ocean or adding the motion to the moon. I can combine the two shots by creating a matte with a couple of dozen techniques. From what you've said you've chosen to key out the sky. I probably would have keyed out the moon or simply used a blend mode to add it to the ocean shot. Without seeing either I can't tell what would be easier. If the camera is fairly stable for the ocean shot it's probably easier to remove the motion or stabilize the footage, but it may be more interesting to add movement to the moon.
Third Step: Track the shot of the ocean. Without seeing the shot I can't tell you which tracker would be best. There are at least 6 possible solutions inside AE and dozens more with 3rd party software. Once you get a good track decide what to do with it. If there's some kind of stable plane in the shot (like the shoreline) I'd probably track that plane in Mocha, then add the motion of that track to the moon. Then I'd lay the moon on top of the footage so that both were shaky.
So there you have it. 3 simple steps to a successful shot. The problem with my answer is that without seeing your footage and talking more about what you want to achieve I can't give you any better answer. There are just too many ways to do it. BTW, all of them require more than a basic knowledge of After Effects.
Mocha sounds like a good option for adding the same movment to the moon. Here's a tutorial that might be helpful.