Что я должен добавить к программе C# для него, чтобы искать и обновить себя каждый раз, когда это загружается?
Проверьте Click Once: http://msdn.microsoft.com/en-us/library/142dbbz4%28v=VS.80%29.aspx
Если вы хотите сделать что-то сложное или невозможное с помощью ClickOnce (которое включает в себя большинство нетривиальных задач), ознакомьтесь с AppLife Update.
Существует компонент средства обновления приложений .NET от Microsoft, который поставляется с исходным кодом:
http://windowsclient.net/articles/ appupdater.aspx
Я использовал его в нескольких проектах, и он хорошо работает.