I'm not an authority on this, but what you replace is entirely up to you. You don't absolutely have to change them all... or it might turn out that every single last one of them will cause stability problems and you DO have to change them all to make the board work properly.
Generally, all caps that are of the same exact type are likely to have the same underlying problem (bad electrolytic being used in caps was a huge issue from 2000-2007 roughly). Caps of the same brand but different sizes are likely not far behind the others... but there's no way to know for sure.
It's also worth noting that heat tends to make caps fail prematurely, which may be why you're seeing physical signs on the ones by the VRMs and CPU (hottest area of the board). I have an Abit IS7 board with all good name brand caps (Rubycon I think... can't remember), but one single cap near a voltage regulator is swollen. Likely, the way the board is designed, most of the heat from that regulator is absorbed by that capacitor, which caused it to fail in a way that the other similar caps won't for a long time (or maybe they're all bad... who knows). When I get around to fixing this board, I fully intend to just replace that one first. If the board is stable after that, I'm not replacing the rest of them unless I have an issue later.
If you're extremely good at replacing caps on modern boards, and you can remove all the caps from a board with a radioshack soldering iron and some braid in less than an hour... by all means, do the whole board. But if you're like me, and even with decent tools you find working on modern (lead-free solder, multi-layer PCBs, tiny solder pads) boards tedious and risky, I'd certainly minimize the amount of times you have to jab it with a hot iron. For most mortals, every component replaced comes with the potential risk of a mistake that can either ruin the board or require more repairs (lifted pads, broken traces, overheated components, etc.).
Of course, when it comes to ordering replacement parts, it's up to you to decide whether you should just order all the caps for the whole board and hope you end up not needing them all... or save the time and money and just order the ones you need, and then order more later if you need to recap others. To be on the safe side, if they are a crappy brand or are of a known bad series from a good brand, I'd replace all of the ones that are identical to the ones that are visibly failing. If any others are the same brand\series but aren't visibly failing, I'd order some of those too. I tend to not worry as much about the tiniest electrolytic caps, because I have yet to come across a board that was dead until I replaced one of those. That's just me though. I'll likely replace them on some boards eventually... I just mainly hate working on modern boards.
Worst I've ever had to work on was an Abit A8N-SLI 32X. I'm not a pro, but I could never seem to get enough heat into the solder joints to make a good connection. There is so much extra metal in that board, it just soaked it all up. I have better techniques and tools now (a heat gun to preheat the board before removing each cap) but I wouldn't wish those repairs on anyone who isn't experienced with this kind of thing.