I think one of the main differences will be that Gnome tends to hide settings/configurations from the user (with the idea of making it easier), Kde tends to show most of the settings available and lets the user customize them (with idea that more customization might appeal more, than less)
Other than that, it is more a matter of styles/themes/colors and general shortcuts (hotkeys), and some different applications for similar functions, eg screen magnification ..They both work..
KDE has a new desktop look, kde 4x, which is more akin to Vistahttp://www.kde.org/http://kde.org/announcements/announce-4.3-rc2.php
Gnome has a look that is more akin to a MAC menus structure (Places, Applications) at the top of the desktop
--fortunately (because I wouldn't be using Gnome otherwise, Mint doesn't adopt that style, they are more like a combination of kde 4x (vista like menus + Gnome categories (All, Favorites, instead of the standard Gnome look..http://library.gnome.org/misc/release-n ... #rndesktop
And they are also other windows or desktop manager choices, like xfcehttp://www.xfce.org/