Super Mario Sunshine is very similar to its predecessor, Super Mario 64, in that the gameplay is quite open. There is a central area (Delfino Plaza) and several "adventure" areas which branch off from it. These areas are where the more traditional gameplay takes place. Because of this, any walkthrough has to be pretty non-linear as well, so there is no need to follow the steps in the exact order they are shown here.
So, the story begins with Mario and friends making their way to the sunny beaches of Isle Delfino, only for them to find the island in crisis. It has been covered with graffiti and the island's energy source, the Shine Sprites, have been scattered all around. It's now down to Mario to help the islanders return to their normal lives. After the intro movie, Mario and the crew have landed at Delfino Airstrip, but something's not right...