You click the "cashew" icon, then click and hold on the Screen Edge button and move it where you want: top, left, right, or bottom.
KDE 4.x has taken a new direction in what the desktop does and means. You can customize it in so many ways, it'd be hard to list them all.
One of the ways you can customize it in dozens of ways involves what you're calling the toolbar/menu. In KDE, this is a panel. You can then place things called widgets on the panel. Most default configurations I've seen include a taskbar, a "quick launch" widget, the system tray, a clock, and the kicker or Application Launcher widget. In Windows, the whole thing is called a taskbar. Every time you open a window, this "task" is represented on the taskbar. The taskbar widget works the same in KDE. The quick launch widget is the same as the quick launch in windows, etc. The "kicker" is analogous to the Start Menu.
The Add Widget menu showing a small sampling of some of the widgets
One new aspect of this is that you can have multiple panels. I've seen systems with a panel on the top and bottom. This allows you to do various setups, like having one panel for the taskbar, one for miscellaneous other things. Hell, you could have one on each edge. I dunno why you'd do that, but you could.
Also, you can add the widgets to the desktop itself, which in KDE is called the Plasma panel. This means you could put the taskbar smack in the middle of your desktop if you wanted. In fact, some of the widgets only really function properly while on the desktop.
The other major difference with KDE is that the desktop is no longer intended to hold a bunch of icons. You *can* do that if you want, but it's not the point of it anymore.
You can use the desktop to display various widgets (like a system or network monitor or those mentioned previously), various folder views, and the icon shortcuts if you want.
Here are the various folder views you have. The first is the default view, showing the contents of my home directory. The one beside it is another kind of view showing the contents of my ~/bin directory. The third is an icon linking to my ~/archives directory.
You can also create a blank one of these and populate it with whatever you want, sorta like that program for Windows mention in another thread that allows you to organize your desktop by grouping things together.
I'm not really qualified to tell you all the differences between GNOME and KDE specifically other than to explain things about KDE. I've used GNOME very little because I don't like its "look and feel." That, for many people, is the practical difference between them.
There's also the matter of applications. GNOME is based on the GTK library, KDE on QT. That matters only in the sense that these libraries are used to make the GUIs for various apps, so you have "KDE" programs and "GNOME" programs. That does *not* mean you can't use a "GNOME" application under KDE or vice versa. It just means that when you install KDE or GNOME, you generally get a different set of default applications, e.g. Konqueror or Dragon (Mint uses Dragon) for the file manager, Nautilus in GNOME.