"Themes" are visual changes to your GUI (Graphic User Interface). That is the most straight forward answer to your question.
When you look at your phone, you will see many things. The background on your phone. The status bar across the top. All of the little notifications inside the status bar. The sliders and buttons for your lock screen. The clocks. The list goes on. Each one of these items you see are actually a PNG file... a picture file. Themes will change these pictures so they have a completely different look. There are three ways I know of to achieve this... Ranging from being very user friendly to risking damage to your phone.
The first, as stated above, is using a home replacement app. A great deal of things can be changed by doing it this way. There are a few drawbacks, though. For starters, it won't be able to change the look of your status bar or notification icons. As far as I know, you also can't change the look of things like your dialer by going this route. Most importantly to those users who want it to be 100% theirs and no one elses... your themes are limited to those themes that other users have created and can be downloaded.
The next two methods require root... or Super User access. There are a ton of threads on what that is and how it works, so I won't get into it here.
As CRPercodani said, one of the next methods is by using a program called "Metamorph". Since it requires root access, this means that you now have the ability to change things like the statusbar and icons, your dialer, your contacts list, or any other part of your phone as well... you are no longer limited to just the home screen. The obvious downside to this is that, like the home replacement app, you are limited to themes others create for you. You do, however, have the ability to mix and match themes. For example, you can use a statusbar from one theme, the icons from another, a dialer from a third, etc.
If you wanted the absolute most customized phone, then you could just create your own theme and icons for Metamorph, but a lot of people (myself included) would, at this point, just change the PNGs and just manually add them on your system where it needs to be. The obvious drawback to doing this is that this is where things start to get dangerous for your phone. As a few users have found out by now, all you would have to do is compress the folder the wrong way, type something wrong, or save a single picture as the wrong format, and your phone will not come back on when you reboot. You will have to use a recovery image to get it to work again.
And just in case I hadn't made things clear enough, I'll throw in some pictures so you can hopefully see what I am talking about more clearly.
http://img205.imageshack.us/img205/1424/92679823.jpg
(Linked picture so I didn't have to resize.)
This is a picture of my framework-res folder for the theme I've been working on for my phone. You will notice that the statusbar icons have been changed on a great deal of them. Compare your phone and your icons to the ones you see here.
Now, here are a couple of pictures of my home screen. This is where you can see the new icons... or "Theme"... in action.
If there was something I missed, feel free to ask more questions. I will answer them the best I can.
In order to use themes on our Droids you need to be using one of the home replacements like OpenHome, GDE , or the like. Then you can download the themes from the market and install though the home replacement menu. The default home doesnt have themes like we were used to with our BlackBerrys.
Just didn't want us scaring off the new guy (bryston). He was just trying to help the best he could. 
I am, by no means, an expert in here. I marvel at the knowledge some of these guys have. It's great that we can all come here and learn together.
