Super Mario Sunshine is very similar to its predecessor, Super Mario 64, in that the gameplay is quite open. There is a central area (Isle Delfino) and several areas which branch off from it. These areas are where the more traditional "levels" of the game are based. 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.