Any pitfalls when going from two to four layer PCB?
It's not that much different to design for 4 layers compared to 2.

A couple things I can think of:


If you are running very large currents, tracks on the inner layers have higher thermal resistance to the ambient air, so need to be designed wider for the same ampacity.
You need to make more decisions about the stack-up. Do you want a thick middle dielectric layer and two thinner outer dielectrics, or the other way around. Do you want the inner dielectric to be a core with two pre-preg layers laminated on (foil construction, because the outer copper layers will be "foils" laid onto the unclad outer layers); or do you want a pre-preg sandwiched between two cores (I forgot what this is called). Specify all the dimensions and which layers are core or pre-preg on your fab drawing.



  Can you jump from any layer on the board to any other or only to adjacent layers?


Unless you want to pay extra, you will connect between layers using a drilled hole ("via") that goes all the way through the board. You can connect to that via on as many or as few of the layers as you want.