While development on a direct sequel to Kingdom Hearts began shortly after the first game turned out to be a massive success, the next game in the series actually debuted on the Game Boy Advance. While at first glance, Chain of Memories seems like the odd duck of the franchise, with its emphasis on card-based combat (hey, it was the early 2000s, and card battle systems were in vogue). However, this game is actually a pretty critical part of the overall Kingdom Hearts story, bridging the gap between the first and second game. And it's pretty fun in its own right!
At the end of their journey from the first game, Sora, Donald, and Goofy are still on the lookout for the missing King Mickey and Riku. After running after Pluto, who has a letter bearing the king's seal, the trio finds themselves in the mysterious Castle Oblivion. There, they encounter a group of enigmatic black-robed individuals calling themselves The Organization (later known as Organization XIII, these guys serve as primary antagonists across several of the other games), who inform Sora that as he proceeds through the Castle, his memories will slowly fade away; however, something long lost to him will be restored. This "something lost" is Namine, a girl who greatly resembles Sora's friend Kairi and is being held captive by an Organization member named Marluxia so he can use her memory-altering powers to manipulate and control Sora and, by proxy, the Keyblade. After Marluxia is defeated, Namine offers to put Sora and company into a deep sleep and restore their missing memories, which is where Kingdom Hearts II eventually picks up. After completing the main story, the player can go through it again as Riku, which offers a unique perspective on the game's events as he struggles with the darkness inside him and eventually meets the mysterious DiZ, who has a vendetta against Organization XIII.
Chain of Memories is still an action RPG at its core, but unlike the one-to-one action combat of the PS2 game, this portable adventure uses a card battle system. Sora has a "deck" of cards that represent various actions: individual attacks are Keyblade cards, and other cards have Donald, Goofy, and other characters on them, and can be used in combination with one another for various one-off attacks. Each card has an attack value associated with it, and the player will have to contend with cards played by the enemy they're battling as well: playing a card with a higher number of a suite of multiple cards will override the enemy's cards and open them up for attack. It's a fairly simple and intuitive system that offers a unique dimension to combat without completely changing the game feel of the original game, making it feel a lot more like an "authentic" Kingdom Hearts title than it may appear at first glance.
The entire game is set within the confines of Castle Oblivion, and it's a much more linear affair this time around: there's no overworld map or Gummi Ship levels to take part in, and instead Sora will go through facsimiles of worlds from the original Kingdom Hearts set up throughout Castle Oblivion. These "worlds" are made up of procedurally generated "rooms" that play like a mini Kingdom Hearts level, with platforms, enemies to fight, and treasure chests to uncover. The player actually can influence the properties of the next room they enter using room cards, which can determine what kind of room will be behind the next door: one with more treasure, for example, or more powerful enemies, or a save point. Certain rooms have event scenes that allow the player to progress, eventually culminating in a boss fight and the next major story sequence. It's a little... redundant, at times, since the event scenes in these worlds are basically straight retreads of the Disney worlds from Kingdom Hearts (which, unfortunately, is a trap a lot of the spin-offs fall into), which means a large percentage of the game is inconsequential to the narrative at hand. Still, I actually thought this procedural generation system was kind of fun, if a little simplistic.
Chain of Memories was actually remade for the PlayStation 2, and packaged with the Japanese Final Mix edition of Kingdom Hearts II. Re:Chain of Memories renders the entire experience in 3D, unlike the 2D sprites of the Game Boy Advance version, with fully voiced cutscenes and other tweaks and additions to improve the experience. While the GBA version remains a curiosity item, nowadays Re:Chain of Memories is the way to go, and is the version packaged with the ReMIX compilations. If you really can't be asked to mess around with the card combat and just want to experience the story, though, I would actually really recommend the manga adaptation of Chain of Memories: it's only two volumes and a pretty succinct retelling of the game's story that can help get you up to speed for Kingdom Hearts II.