There are quite a few differences really, but on the user side of things, you shouldn't be concerned with them, not yet anyway. Simply:
* They both work independantly of each other (what this means is you can run GNOME apps in a KDE environment without much of a hitch);
* They are currently (not by far though anymore) the 2 largest contenders in Linux Desktops Environments. They are about as "generic" when referring to as things come with linux. KDE3 should perform the same functions as KDE3 on any box you use if setup default (or changes are the same on both boxes).
* The "look" will be what you should notice to be the difference. Also, the way the Control Center controls the DE (Desktop Environment which is what KDE and GNOME are) functions such as startup and shutdown are similar yet slightly different.
* Themes will be specific to each as they are setup differently (one uses a completely different graphics utility than the other to serve it up to the X server and out to you) so if you find a theme you like, it will usually only work in the DE it was specified for and written for.
The pluses are:
They have an amazing easy to use GUI for administering the system for a newbie. As well as great tools to assist in learning how to use different aspects of your system.
They are also very nice/easy to make "look good" and for one to control simple functions with.
* Pretty much just the slowness you'll find. They aren't as fast as the smaller window managers (wm) that can be used (but have significanly less features) independantly of any DE.
* Some argue that they hide the system from the User, restricting them from "learning" linux. This is arguable depending on the situation...