Hi
Elviriel, welcome to KHInsider.
With both HD Remixes already released and owning a PS3 you can literally experience 90% of the series from the get-go if you do opt for the HD Remixes.
Another fact speaking for the Remixes is that they include the
Final Mix-versions of the main games, Kingdom Hearts (I), Kingdom Hearts II and Birth by Sleep. Extended versions of these games previously exclusive to Japan which provide a more complete experience.
For the order to experience the series in it would be best to start with the games in release order, which means starting with KH HD 1.5 Remix.
In there, you'll want to play Kingdom Hearts Final Mix first, which is the original that started it all back in 2002.
After that comes Re: Chain of Memories, which is a bridge game between Kingdom Hearts and Kingdom Hearts II and introduces some characters and plot points important for the further story.
Some people even tend to say that many of the deeper going problems (both in-story as well as in terms of complications for understanding) start with CoM.
Last but not least in 1.5 is Kingdom Hearts 358/2 Days, which covers the entire period between Kingdom Hearts I and II (roughly a year) from the perspective of other important characters in the series. In fact, Re: Chain of Memories takes place
during 358/2 Days and you'll easily see when.
From a story perspective it is however definitely better to start with Re: CoM, also since 358/2 Days was not remade into a playable game but a sort of HD cutscene movie.
If you want to play 358/2 Days as a game, you would need to get the original Nintendo DS-game (which btw also works on a 3DS).
Continuing then with HD 2.5 Remix, next game in line would be KH 2 Final Mix, where many open questions from KH I and Re: Chain of Memories are answered but in the process more and deeper running mysteries get unveiled. The Final Mix version of KH II also holds a great special secret ending in store that foreshadows Birth by Sleep, the next game in line to be adressed.
Birth by Sleep takes actually place ten years before the first KH, and helps to understand many of the workings of the KH series so far as well as finally revealing the main villain behind it all. The secret ending of BBS is not as bombastic as the one of KH II, but gives a great wink in which direction the series is headed and what can be expected in the future.
Last in line would be then Re: Coded, which takes place chronologically a week or so after KH II and gives the first substantial glimpses towards what awaits in the future.
This one however is, like 358/2 Days, a HD cutscene movie and if you want the game and actual gameplay you'll need the original DS-game.
So in short, the ideal order to play/follow the series is:
1. Kingdom Hearts Final Mix (included in 1.5 Remix)
2. Re: Chain of Memories (included in 1.5 Remix)
3. Kingdom Hearts 358/2 Days (included in 1.5 Remix)
4. Kingdom Hearts II Final Mix ((included in 2.5 Remix)
5. Kingdom Hearts Birth by Sleep Final Mix (included in 2.5 Remix)
6. Re: Coded.
Some people advise to play in chronological order, meaning to start with Birth by Sleep, but that is not really recommendable because a) many of the "aha"-moments in Birth By Sleep connected to the rest of the series go either unnoticed or make no sense to new players who play it first and b) it could give false expectations concerning the protagonists of the series.
Birth by Sleeps three main characters are indeed important main characters in the series of their own, but the actual main
protagonist of the series is Sora, who in BBS has only a minor (albeit important) role as a four year old kid.
Now, there's still one game left to address, and that's KH Dream Drop Distance which so far is exclusively for the Nintendo 3DS.
DDD takes place the farthest in the future of the timeline, after Re: Coded, and is thus the last title you should pay attention to when it comes to story.
In fact, DDD weaves together the all the parallel plotlines from the previous titles and acts as a sort of Prologue for KH III itself.
If you're truly considering getting a Nintendo 3DS you would be truly set to experience the whole series so far, as it can be done with a PS3 and 3DS in tandem.
That was quite long now, but I hope helpful nonetheless.
PS: Yes, the overaching story is considered to be quite complicated to understand, but the main reasons for that are that a) main series creator Tetsuya Nomura likes to make things "surprising" and thus tends to adds more story twists and vague concepts than necessary and b) only ca. 60% of crucial information for understanding the story can be gained by the games and their internal reports themselves. Around 40% of crucial facts are only found in japanese only Ultimania books and interviews with series creator Tetsuya Nomura.
Luckily our main site at KHInsider has an archive where most important Nomura interviews are available with translations.