Let's change this to steps.
- Beat the main game. This gives you access to Routes 1 to 3, and surrounding cities and towns.
Go to Route 1. You will find a small area with water that you may Surf on. Follow the stream. At the end of the hilly area, you'll find a gate building that leads to Route 17.
If this is at all confusing, look at this for directions.
- You will find yourself at Route 17, where you shall Surf again. The water on Route 17 is full on currents, which means you will have to choose wisely which current to ride on. Navigate your way through.
- If you want the right way, you will find a small island with a little building on it; the P2 Laboratory. Another notable presence is the Plasma Frigate, which is docked nearby the island. However, if you find yourself at a large island, you're at Route 18; wrong way.
For complete directions, see this:
It will guide you to the P2 Laboratory, beginning at Nuvema Town.