KDE stands for the K desktop environment, and Gnome stands for the GNU network object model environment. Both are two possible GUI's that can be used with Linux. KDE was created first, and there were two projects started. One, in particular, was set up to replace KDE because it's the reliance on Q+ toolkit was concerning to the open-source community.
The other project was to replace the toolkit. The gnome was built from scratch using the GTK+ toolkit, which is entirely under the GNU. Gnome has obtained a substantial following, and it was no longer focused on the toolkit, and Gnome progressed. The difference between the two environments are mostly insignificant and do not have any effect on how the operating system works.
However, many users who are beginning the transition to Linux are often discouraged when using KDE. Gnome keeps things simple, which helps to dispel confusion; however, advanced users feel the environment is limited.