The main difference is that KDE is C++ with Qt, while Gnome is C based on top of GTK.
Then you have the windowmanager that has a different philosophy on what to show the user.
And then you have the applications that that is just different...
Update: They are both good nice and stable (if you select the right versions).
They can do approximately the same but in different ways, so it is hard to compare.
My personal view is that Qt is a nice framework to write software with,
but I also know that there is a lot of guys that would say exactly the same for gtk.
Since this is the topic for a classic flamewar, there is a lot written all over the internet on this topic.
But when it comes to embedded the answer is simpler, since Nokia (the phone maker) is now the owner of Trolltech (the maker of Qt), they have pushed Qt to become a valid choice for embedded. And there is now a version of Qt called "Qt for embedded linux".
And they created a new distribution with Intel and the Linux Foundation called MeeGo.
So Qt has a lot of support in the Embedded realm, and it has a quite good documentation so it is easy to get started.
A example that you can look at/use is MeeGo on the BeagleBoard.