This part of the game is a bit unintuitive (I'm hoping to implement a main questline in the quest journal to make it easier to keep track). In the current absence of such a questline, here's a step-by-step guide:
1) Enter the Sand Swamp from the left side and immediately turn down. You should find yourself in an area that was previously inaccessible due to a skeleton standing in the way. Beyond this area are the Thunder Highlands (part of the world map). Take the opportunity to travel to the small dock at the bottom of the Highlands and talk to the green-robed figure (his name's Vico and he'll join your party).

2) Go to the big mountain on the right side of the Thunder Highlands. This is the Thundercrag and is a mini-dungeon at the top of which you'll find a stranded neko named Natasha. Rescue her and make sure to read the dialogue, since she'll offer to meet you back in Windrush Canyon, on the roof of the Racing Commons.

3) Meet Natasha on the Racing Commons roof. There will be a brief dialogue after which she'll ask you to meet her at the lighthouse across the water from Costa Del Nyan. It's next to Leslie's House on the World Map, in the wide open fieldy-area on the very right-hand side of the same continent as the Sand Swamp and Thunder Highlands.

4) Meet Natasha at the aforementioned Lighthouse and she'll lend you a stonebird to reach Split Palm Island, which is your ticket to eventually reaching the Air Temple. Things should be fairly straightforward from there (and you'll receive a travel gem once you go to the island so you can return to it from anywhere on the World Map).