We used KDE as an example, but it's by no means the earliest desktop environment for Unix systems. Perhaps one of the earliest is CDE (Common Desktop Environment), another sibling of the OSF. As per the CDE FAQ: "The Common Desktop Environment is a standard desktop for UNIX, providing services to end-users, systems administrators, and application developers consistently across many platforms." The key here is consistency. However CDE wasn't as feature-rich and easy as it needed to be. Along with Motif, CDE has practically disappeared from the free software world, having been replaced by better alternatives.
Under Linux, the two most popular desktop environments are KDE and GNOME, but they're not the only ones. A quick internet search will reveal about half a dozen desktop environments: GNUStep, ROX, GTK+XFce, UDE, to name a few. They all provide the basic facilities we mentioned earlier. GNOME and KDE have had the most support, both from the community and the industry, so they're the most advanced ones, providing a large amount of services to users and applications.
We mentioned KDE and the components that provide specific services under that environment. As a good desktop environment, GNOME is somewhat similar in that. The most obvious difference is that GNOME doesn't mandate a particular window manager (the way KDE has kwm). The GNOME project has always tried to be window manager-agnostic, acknowledging that most users get really attached to their window managers, and forcing them to use something that manages windows differently would detract from their audience. Originally GNOME favored the Enlightenment window manager, and currently their preferred window manager is Sawfish, but the GNOME control panel has always had a window manager selector box.
Other than this, GNOME uses the Gtk toolkit, and provides a set of higher-level functions and facilities through the gnome-libs set of libraries. GNOME has its own set of programming guidelines in order to guarantee a consistent behavior between compliant applications; it provides a panel (called just "panel"), a file manager (gmc, altough it's probably going to be superseded by Nautilus), and a control panel (the gnome control center).