If I recall correctly, you need to receive a call from Prof Oak so he can tell you about a new ship ticket. I received his call when I was in New Bark, in front of home, but I don't know if it needs to be there. Anyway, after he talks to you, just go to that new building in Vermilion and get your new ticket. Then you need to go back to New Bark and surf south, to a new route, to find the Orange Islands Gate - Undersea Express.
Ok, thank you very much for the quick answer, now I can play again!