Pre-Linux time, I never used to worry much about how my desktop looked. Mostly, this was because XP was, and still is, very limited, without 3rd party programs.
Linux, on the other hand, has unparalleled choice.
Originally, I used XFCE, which of course uses practically the same things as GNOME, which I later used.
Both of these, in comparison to XP, held that much choice, and I changed how it looked often.
At the time, I used one tool - Art Manager. It's a Ubuntu (And probably Debian too) package which you can get GTK, Metacity and more themes.
KDE I experimented with, but as I've said before, I don't like it as much as I do GNOME.
Since discovering the useful site gnome-look, I've found even more choice, and I've since moved from the Metacity window decorater to using Emerald, or Beryl Emerald, to be exact, because it has many interesting styles that I like.
Some people seem to have trouble getting Emerald to work, so, thanks to many people online, and many hours of searching and investigating, here is how to do it.
Firstly, you need to install the Emerald Theme Manager and it's dependencies. Also, Compiz-Fusion should be installed too. Finally, look for the package compiz-fusion-icon (or something similar).
The Fusion Icon is invaluable, as it sits in your notification area, and you can launch both Emerald and Compiz settings managers, change your window manager and window decorator... very useful.
(A Caveat - While running the dev version of compiz fusion, changing the window manager while logged in causes the X session to become unresponsive. I'm not sure if this is my computer, the dev version of compiz, or just me fouling up, so be aware it may happen to you too)
Second thing to do. Launch the Compiz Icon. You'll find it (In GNOME) under Applications -> System Tools -> Compiz Fusion Icon.
Right click on the icon that appears in the notification area, and select Emerald Theme manager. Choose your theme, set any option. Note that at this point you will NOT see any change. This is normal.
Close the Emerald Theme Manager
Right click on the Compiz Fusion Icon again, this time go down to Select Window Decorator, and in the submenu that appears, select Emerald.
Et voila! Give your computer a few moments (or nano-moments if you've got a blindingly fast box) and Emerald should be working normally.
If, for some reason, it isn't, then you need to do a little more.
Go into System -> Preferances -> Startup Applications (Or Sessions, on older Ubuntu versions)
Add an entry, give it the name 'theme' and make the command 'emerald --replace' both without quotes (Copy and paste from here if you want to be sure)
Reboot, or log out and back in, and that should have fixed it.
Now enjoy your Emerald themes. Hope this helps!
Oh, and as a last note, completely unrelated... I now strongly reccommend you miss a bus than run for it - tripping and sliding along the pavement, or sidewalk, or whatever you call it, is not only painful, it leaves you with a lovely arrangement of grazes, bruises, and in my case, also a split lip. Not fun.
Rock on people.