From Bulbapedia, the community-driven Pokémon encyclopedia.
After the credits roll through, the game resumes a few mornings after you convince Rayquaza to destroy the star. You might think that all you can do now is to do rescue jobs for eternity, right? Wrong. There are many new dungeons to explore, and new Pokémon to meet.
After exiting your base, Caterpie and Metapod come to your base with a problem: Snubbull has completely changed appearance! You and your partner track down Alakazam and a very confused Snubbull, who is now a Granbull. Whiscash shows you a cave that Granbull went into, and Alakazam explains about evolution. You and your partner want to evolve, but the cave only allows one to enter. Fear not, because when you head to the dungeons path, your partner will give you the option to dismiss a team member, enabling you to enter Luminous Spring. Evolve anyone who's ready, then head back to the base.
On the path from your base to Pokémon Square, you will find Medicham. Listen to its rant about Lombre, then head to Pokémon Square. Talk to Lombre, and he'll tell you about about a dungeon in the sea. Now visit Whiscash in his pond, where he will explain about the new dungeon, Stormy Sea. Whiscash will give you your first HM, Dive. It is needed to enter Stormy Sea, so teach to a party member or keep it in your toolbox. (The latter is preferable, since Dive can only be used on water terrain.) Whiscash will also unlock Solar Cave.
The dungeon is 40 floors, with no save point in the middle.
On floor 40, you'll find Kyogre.
Kyogre can be recruited the first time you battle it, so make sure to send home team members until your team size is two stars or less.
Several days after completing Stormy Sea, you receive a letter about the Buried Relic. After reading the letter, talk to Lombre in Pokémon Square, then follow with Shiftry. Shiftry will grant access to Buried Relic (after making you and him compadres).
In the Dungeon
This dungeon has several things to be on the lookout for. It is the first dungeon you find with 99 floors, so prepare accordingly. There are three bosses: Regirock on B15F, Regice on B25F, and Registeel on B35F. After being defeated, the Regis will drop the Rock Part, Ice Part, and Steel Part, respectively. When the three are in the toolbox at the same time, they form together to make the Music Box. Keep this in your toolbox, and Mew will appear between floors 36-98. Finally, four HMs can be found here: Rock Smash on B45F, Strength on B60F, Flash on B70F, and Cut on B80F. Rock Smash and Strength are behind locked doors, so bring keys for those floors. Flash is behind a wall, so switch to a Ghost Pokémon or bring a Pokémon that knows Rock Smash. Cut needs both a key and a Pokémon that can smash or pass through walls, plus a Pokémon that can travel over water.