So last few days I've been working on my first iPhone theme and since we have 5 kids and one computer it's been slow going. The good news is you can do 90% of it right from your iPhone.
I started by just downloading the pics I wanted from the Internet and then realized I could go on YouTube and take screenshots of the things I wanted as icons and other images.
Then I use iretouch lite to crop and resize and PS mobile to add boarders. Then use ifile to move and rename everything in my new theme folder. You can also you dtunes to get music and add your ringtones and SMS. Here's a preview: