Palkia can be found on the Spear Pillar as a guaranteed encounter during the storyline of Pearl version.
Legendary. Guaranteed encounter. One (rare) weakness. These words all describe one of the most useful and absolute best Pokemon you can get in a Nuzlocke run - Palkia. With an enormous movepool, extreme offensive and defensive power, and the essential guarantee of getting one via Master Ball, one would be crazy not to pass up this Pokemon for the endgame.
Gym #8 - Volkner (Sunyshore City, Electric-type): If you're using a Physical Palkia, use Earthquake on Raichu and Luxray, and Dragon Claw on everything else. If using Special Palkia, Spacial Rend should do the job.
Rival (Pokémon League): Palkia has a wide variety of moves that can do the job to any and all of these Pokemon. It can learn Flamethrower for Torterra and Roserade, Thunder or Thunderbolt for Floatzel, Staraptor, and Empoleon, Water Pulse or Surf for Rapidash and Infernape, and Spacial Rend for Snorlax and Heracross. And none of Barry's Pokemon can hit super-effectively, so even if you don't secure an OHKO on everything, you'll be fine.
Elite Four Aaron (Pokémon League, Bug-type): If your Palkia packs Flamethrower, you are all but set for this fight, considering the majority of his Pokemon share a Fire-type weakness. If not, Spacial Rend serves as a powerful-enough substitute to knock out his Pokemon.
Elite Four Bertha (Pokémon League, Ground-type): Using Water Pulse or Surf will secure victory against Golem, Sudowoodo, and Hippowdon. For Whiscash and Quagsire, using Spacial Rend is the recommended strategy. Just remember to watch out for Whiscash's Fissure attack if your Palkia is not yet Level 55.
Elite Four Flint (Pokémon League, Fire-type): Water Pulse or Surf doesn't go as far as you would think in this fight, since Flint only has 2 Fire-type Pokemon. However, it can be used to knock out Infernape, Rapidash, and Steelix. As for the other two, Drifblim can be defeated with a Thunderbolt or Spacial Rend, and Lopunny, being the frail Pokemon it is, should easily be taken down with one Spacial Rend. Keep wary of Mirror Coat, however, as one failed kill against Lopunny could spell disaster for Palkia.
Elite Four Lucian (Pokemon League, Psychic-type): If your PP hasn't run out already, or you have extra Ethers and Elixers on hand, Spacial Rend is an effective tactic in this fight against Alakazam, Girafarig, Medicham, and Mr. Mime. However, against Bronzong, it might be better to use Flamethrower.
Champion Cynthia (Pokémon League): You will have to use quite a few of Palkia's skills to take down all of her Pokemon. Spiritomb will be 2HKOed by Spacial Rend, Flamethrower will 2HKO Roserade, Spacial Rend guarantees a 2HKO on Gastrodon, and Flamethrower is a guaranteed OHKO on Lucario. Milotic is, perhaps, the toughest Pokemon for Palkia in this fight. Spacial Rend is a 2HKO, but it leaves Palkia wide open for the deadly Mirror Coat attack. Garchomp is another dangerous target, but not quite as dangerous as Milotic. Garchomp outspeeds, and Dragon Rush is a guaranteed 2HKO on Palkia, leaving you open for a critical hit or a flinch. If you do risk it, however, Spacial Rend will certainly OHKO Garchomp if you're rolling with a Lustrous Orb.
Upon catching Palkia, you are graced with Spacial Rend, Water Pulse, Dragon Claw, and Ancient Power. Shortly after the capture, at level 50, it will try to learn Heal Block. Don't let it learn Heal Block, it is worthless. Level 60 will give Palkia Earth Power, which provides a bit of enhanced coverage. If you are bringing Palkia into the post-game, it will learn Slash, Aqua Tail, and Aura Sphere at levels 70, 80, and 90, respectively. But honestly, if you're grinding Palkia up to those levels, then you're probably already one-shotting almost everything.
As expected of a legendary, there is quite a wide array of moves that Palkia is capable of learning apart from level-up. From the Game Corner, it can learn Thunderbolt, Ice Beam, and Flamethrower. It is also possible to teach it the less-accurate but more-powerful Department Store TMs, Thunder, Blizzard, and Fire Blast, although Palkia's already-high Special Attack should suffice with the use of the first 3 moves. On the HM front, Palkia is a handy Surf user, if you prefer sacrificing the confuse chance of Water Pulse for increased power. If you would rather run a physical attacking Palkia, for some reason, it can learn several of those moves, including Stone Edge (from Victory Road), Rock Slide (from Mt. Coronet), Earthquake (from Wayward Cave), and Brick Break (from Oreburgh Gate).
Special: Spatial Rend, Surf, Flamethrower/Fire Blast, Thunderbolt/Thunder/Earth Power
Physical: Dragon Claw, Stone Edge/Rock Slide, Earthquake, Surf
Steel-types: Water/Dragon is one of the best defensive types in the game within Generation 4, outmatched only by Ghost/Dark, by having only one weakness - other Dragon-types. Even though there is really only one major Dragon-type in the game (see: Cynthia's Garchomp), it's ok to have a Steel-type as backup for Palkia in the rare situation that it has low health and is stuck against a faster Dragon (again, see Cynthia's Garchomp). Just be careful that you don't run that Steel-type against a Ground-type attack (once again, see Cynthia's Garchomp) unless it has Levitate.
Minimum stats are calculated with 0 EVs, IVs of 0, and a hindering nature, if applicable.
Maximum stats are calculated with 252 EVs, IVs of 31, and a helpful nature, if applicable.
What Nature do I want? You have one chance at a nature for this Pokemon, so you can't really choose. However, if you are trying to figure out whether or not to run a physical or special set, then you should look at which stat is reduced: If Attack is cut, run Special. If Special Attack is cut, run Physical. If a defense stat or Speed is cut, go for either.
How good is Palkia in a Nuzlocke? It's gamebreaking. A wide variety of moves, deadly attack stats, and bulky defense stats mean that using a Palkia in the endgame of your Pearl means that you will be essentially set for your final fights. Unfortunately, the fact that you won't be using it very long reduces the enjoyability. That doesn't mean it isn't fun to watch this Dragon curbstomp many of the final Pokemon in the game.
Resistances: Fire (1/4), Water (1/4), Steel
Neutralities: Normal, Fighting, Flying, Poison, Ground, Rock, Bug, Ghost, Grass, Electric, Psychic, Ice, Dark