In the world record video I've noticed they can spin without having to wait in between each spin when underwater. How do you do that? I've been trying myself but can't figure it out.

I have a vague memory that it has something to do with being right below the surface of the water, so that you're almost jumping out and refreshing it somehow

Are they doing it while deeper in the water too?

Well, when you're underwater, you have no spin cool down in Mario Galaxy 1 only. So to spin constantly underwater, just spin. However, you might be thinking of surface swimming, where you swim right on the surface of the water and gain lots of extra speed. This is basically just what happens when you spin right at the surface of the water. A good video to watch to get to learn more is this:

Ah ok so the secret tech is just furious shaking

EDIT: Any differences between Mario and Luigi?

As far as the swimming goes, no. As far as the game goes in general, yes. Luigi runs faster and jumps higher, but he is slightly harder to control because he's more slippery.