There is a plot between advance wars 1+2+ dual strike ... but not deep or with cliffhangers.
It doesn't really matter the order, they do show some background story at the beginning of each sequel... but you will get bored and not challenged if you play the first game after beating any of the sequels.
Day of Ruin is complete different story and characters altogether.

 

Technically the "wars" series stretches back to the GB and NES, many of the games have also been translated and hacked to be improved/fixed. Though Advance Wars in general is a pretty well hacked game series, http://forums.warsworldnews.com/ being a good jumping off point there.

What I will say is the games depart a bit from their original formula as things went on -- for me they almost started out a bit like chess with a simple moveset but one that was ultimately very rewarding, then they started a shift towards CO powers, CO abilities, added water and air units, added several different types of tanks and many more units (if you follow the gameplay style many would say this is when the series started to mirror aspects of the long time rival franchise daisenryaku). This is not a bad thing and the games were still very fun and balanced/rewarding for those that considered their moves.

 

Running a GBA Emu on your PSP seems like the easiest option.......Love me some Advance Wars