I'm a few days behind in the PSP world as I've finally upgraded my PSP to firmware 3.71 (only a month behind!!) I've found out that among the updates is a new theming option, this allows you to download themes from the web and change the wallpaper and icon sets used in the xmb without affecting the games.
Now for people like me who've had the PSP for a while it's starting to look a little dated, and with the release of the new slim psp this is a good thing as i brings a bit of life back to the machine. I've also managed to find a program that creates the themes, so hopefully one day when i get a bit of time I'll put some icons together and create a theme or two.
In the meantime I've found a site that has quite a few themes for download and you can even use the PSP to get the theme. The site is called pspdemocenter.com