I had the same problem. I'm very new to iphone development and it was my first time trying to load my program onto my iphone. The message is correct, you need to create a certificate in the keychain. The best walkthrough is here:
http://developer.apple.com/ios/manage/overview/index.action
You of course need to have a developer account (need to have paid the $100 yearly fee).
I hope this helps.