In the _system_ folder, there is a theme folder. Open that up, and you'll find 12 folders called theme 1, theme 2, and so on. Every theme has to have a background 1 and 2, as well as a logos and icon images. HAS to be in .bmp format, I think 24-bit. There is also a theme.ini in there. When you want to replace a theme, copy the contents of the folder of the theme you had just downloaded and replace the old files. Do NOT copy the folder into the themes folder, it will not read if you do. Also, there are a mximum of 12 themes. And do not rename the theme folders, keep them theme 1, 2, 3... So here's a kinda directions list on how to get there.
ROOT --> _system_ ----> themes ---> theme 1
contents of downloaded them go into the theme 1 folder.
Go to the downloads section of GBAtemp, and download SimplySkin by JDBye to make your own. Or go to www.ndsthemes.com.