As of November 1st, 2011, this is the chronological order in which the games take place. Credit goes to the Kingdom Hearts Wikia Timeline article. I'll link to the each of the games on the wiki for reference, but if you haven't played them, I'd recommend not clicking these links.
I'm going to divide this into 2 parts: chronological order in which the events in the stories/games occurred and a recommended playing order in order to understand the stories (as best as the KH storyline as a whole can be understood at least... it's... confusing).
- Kingdom Hearts: Birth by Sleep (Playstation Portable) comes first in the timelines, excluding portions of its secret ending, Blank Points.
- Kingdom Hearts (Playstation 2) aka KH1.
- Kingdom Hearts 358/2 Days (Nintendo DS, pronounced "three-five-eight days over two"). Days 1-24 take place at the same time as the finale of Kingdom Hearts.
- Kingdom Hearts: Chain of Memories (Game Boy Advance) aka KH:CoM. Since been rereleased as Kingdom Hearts Re:Chain of Memories for PS2.
- Days 25-27 of KH:358/2 take place at the same time as Chain of Memories.
- While not a separate game, days 28-358 of KH:358/2 take place here in the timeline
- Kingdom Hearts II (PS2) aka KH2.
- Kingdom Hearts coded. Takes place between the ending of KH2 and KH2's epilogue. This was released as a mobile phone puzzle game in Japan only. It's since been rereleased for the NA and EU territories as Kingdom Hearts Re:coded on Nintendo DS.
- Blank Points. This is Birth By Sleep's secret ending. It goes from the end of BBS to some time after Signs of What's Next, the secret ending of Kingdom Hearts Re:coded. The secret ending apparently has spoilers for Birth by Sleep, which is why the final episode for Re:coded wasn't released until after Birth by Sleep.
- Kingdom Hearts 3D: Dream Drop Distance (Nintendo 3DS) It's set after the events of Kingdom Hearts Re:coded.
- Kingdom Hearts III (slated for Playstation 3). Does not exist yet. Development is TBA. We may end up with more games in between before we get to this one.
So, that was slightly confusing. You may also have heard of the various Final Mix versions of the games. These are enhanced rereleases of the game that have additional content in them. However, all of them are Japanese only. :( I'm going to go on the assumption that you only have the NA/EU versions available to you for the recommended play order. If this isn't the case, I'll edit accordingly. I'll also prioritize re-releases over the base games because of the added content.
Recommended Playing Order
- Kingdom Hearts (PS2). Obviously. This is where you'll get the very basis of the story and the heart (no pun intended) of the conflicts. The first "main" game in the story.
- Kingdom Hearts Re:Chain of Memories (PS2, only available for Japan and NA). Alternatively, you could play the original GBA version, which was 2D gameplay, but the PS2 rerelease is full 3D, like KH1 and 2, and also has voice-acted FMVs. It uses a card/deck system for fighting, which is different from the action RPG stylings of 1 and 2, but I still found it quite fun.
- Kingdom Hearts II (PS2). The second "main" game in the story. You pretty much have to play this in order to understand the stories of the prequels/sequels/sidequels/whatever.
- Kingdom Hearts 358/2 (Nintendo DS). Considering the heavy tie-ins with the two main games and CoM, it's best to play this one after them. It's generally considered the weakest game, both story and gameplay-wise by the fanbase, as its plot twist is kind of... weird, but if you want to know everything in lore, I wouldn't really consider it a waste of time, though of course, your mileage may vary. Probably the most skippable if you just want to read a wiki entry on its plot.
- Kingdom Hearts: Birth by Sleep (PSP). This is a prequel, with different characters than the main game (mostly), and is, in my opinion, a must play. Aside from a lot of important story elements, the gameplay is simply fantastic (though I haven't completed yet due to gaming ADD). Despite it being a prequel to the series, I would not advise starting with it, as many of the references and tie-ins to the other games' plots would simply not register.
- Kingdom Hearts Re:coded (Nintendo DS). Though it takes place during KH2's epilogue, because of its secret ending heavily tying into Birth by Sleep's, it's recommended to play this one after that game. I haven't gotten my hands on this one yet, as it was only released in January 2011.
- Kingdom Hearts 3D: Dream Drop Distance (Nintendo 3DS). Taking place after Re:coded, this is where it fits in.
So, in order to have the most complete experience possible, you need to play 7 games across 4 platforms (5 if you play CoM on GBA). Whenever KHIII comes out, that'll bump to 8 across 5/6. While this sounds uh, daunting, personally, I've found it worth it, as even if you don't get completely into the story (and the fanbase kind of accepts its convolutedness at this point), they're still incredibly fun and well made Action RPGs.