After defeating the admin in the Team Magma/Aqua Hideout, you can Surf to Route 124, which leads to Mossdeep City.
Near where you enter Mossdeep City, there is a Big Pearl.
Northeast of the Pokémon Center, use the Dowsing Machine to find a hidden Star Piece.
Talk to the boy nearby to get a King's Rock.
To the right of the launchpad in the northeast corner of the city, use the Dowsing Machine to find a hidden Iron.
In the southeast corner of town, there is a Net Ball.
On the ledge east of the Poké Mart, there is a Revive.
Go into the house north of there to get the Super Rod.
Talk to the girl in the Poké Mart (on the right side) to get TM60 Quash.
In the house south of the Mossdeep Space Center, talk to the Wingull and it will leave to send another message. After this, you can get a Mental Herb from the Pokémon Breeder in one of the houses of Fortree City.
Go into the Mossdeep Space Center and talk to the sailor to get a Sun Stone.
Challenge the Gym
When you're ready, go into the Mossdeep Gym, a Psychic-type gym.