I may be blind or crazy but I can't find the "settings" app on my iPod touch now. Has always been there and I didn't think you could delete it. I have just syncd my iPod and it's still not there. Should I do a restore?
Assuming you didn't jailbreak your iPhone, it's a bug somewhere between iTunes and the iPhone/iPod, I think with firmware 3.1+ -- it happens sometimes when updating the device and/or restoring from backup. When I first set up my new 3GS, it happened to me. The easiest way to fix it is to open the Settings app using Spotlight, as recommended, and then go to General -> Reset -> Reset Home Screen Layout.
You will have to re-configure your icon layout to your liking, but Settings and any other missing icons will be back.