What is a theme?
In the case of the iPhone, a theme consists largely of the way the SpringBoard, dock and all the program icons look. A theme usually change all the default applications icons, the background/wallpaper, the dock and some other elements of iPhone Graphic User Interace.
You can change the iPhone's appearance with a theme and a couple programs. You will need Cydia (it is included in jailbroken iPhones by default) to download WinterBoard and the PC utility iFunBox.
WinterBoard Customization Tutorial for iPhone:
To install WinterBoard, launch Cydia and press the Search button. Enter winterboard in the text box and it should appear as the first choice.

Press it to select it. Follow through with the rest of the installation process and reboot the iPhone when requested. Once installed, you'll see an icon for WinterBoard. There are two ways to launch this program, either press this icon...

...or launch your Settings application where WinterBoard has added its own submenu. I'll cover using the Settings application. Press the WinterBoard menu entry. If you press Select Themes, this is where you can select what you want to modify on the iPhone.

There are many basic themes included by default. Several of them don't work on 4.0 firmware yet. Keep in mind you can combine themes by selecting more than one. You can also change their order in the list. When one theme is higher up on the list than another theme, and they both change the same element, the theme on top will have priority. When you select an item it will have a check mark next to it. Then you press your Home button and the iPhone will respring and load the changes.

The first theme is White Icon Labels. Here is the before and after.

The User Wallpaper and User Lock Background themes have been made obsolete with iOS 4. You now have direct control over what image goes on your lock screen and SpringBoard pages through the Settings application in the Wallpaper menu.
The Transparent Dock theme doesn't work correctly.
The Solid Status Bar theme doesn't work correctly.
Server Lock Example uses an HTML file to call some text from a server and display it on your lock screen.

The Saurik theme has provides an alternate slide to unlock message, and features two wallpaper images that dissolve in and out of each other. I don't like how the wallpaper meets the dock. This theme could benefit from a transparent dock.

No Undocked Icon Labels removes the application name from any icon not in the dock.
How To: Manually install iPhone themes
Connect the iPhone to your PC with the USB cable.
Download to your PC the freeware utility iFunBox from here: iFunBox
Run iFunBox (no installation is needed)
Drag & drop the Theme (folder) to “Raw File System/Library/Themes” see this picture to understand better.
Launch *Winterboard and apply the new theme... done!
*Your iPhone should be Jailbroken, use Cydia to find and install the excellent freeware utility Winterboard.