Easiest:
1. Pour solid copper polygons/planes on the inner layers. This gives a foundation for the signals to work over.
2. Route high speed traces only over the outer layers. And preferably, only on same layer as connector (no layer change -- vias).
3. Trace width depends on impedance, outer dielectric thickness, and dielectric constant. Trace spacing (spacing between P/N in the diff pair) isn't very critical, but does affect it as well.
Typical 4-layer boards are built inside-out. So, a "core" PCB (say 1mm thick) is etched with VCC/GND, then more PCB laminate is placed on either side, and the outer copper foils, and this is pressed and cured. Then the outer copper is etched, holes are drilled and plated, and so on.
The added laminate is your dielectric thickness. Usually 5-10 mils (0.13-0.26 mm) each, giving an overall thickness of 1.6mm or whatever.
The exact dimensions are specified in the layer stackup drawing. If you don't provide one, or you're using a PCB proto service, you'll simply get whatever the PCB fab uses by default. To find out what this is, find the information on their website.
Finally, use a microstrip or differential microstrip trace impedance calculator to find what trace widths you need.
You also need to match the trace lengths, most critically for P/N of each pair. The lengths of all pairs don't need to be very well matched, but it may help.
One final trick:
4. If the trace lengths are very short (much less than the signal's risetime, say < 1 cm), the widths and lengths don't matter very much.
If you don't know any better (or you can't afford any better, such as putting the circuit on a cheap 2-layer board), place the PHY chip right up against the connector, as close as you can route it, including whatever support components (bypass caps, termination resistors?) are needed.
(The dielectric thickness for a 2-layer board is the entire thickness of the board. So, you need very wide traces, ~0.8mm, to get useful impedances. You can't even route a TSSOP component with traces that wide! So for a 2-layer PCB, you have no choice but to make them short.)
Tim