The first thing to do here is to find Steven and meet him. There's a bridge where he can be found a little outside of Fortree. He will use his Devon Scope to reveal a wild Kecleon which immediately attacks. It can be caught. After the battle ends, he gives the Devon Scope, allowing for entrance into Fortree city Gym.
Head back across the bridge where you recently saw Steven, and continue on. As you move down, you'll encounter more trainers.