iTunesに接続し、接続したiPod touchの箇所をクリック
→右画面タブの「アプリケーション」を選択すると、
iPod touchの画面が確認できます。
複数ページある場合はその分だけ選択して切り替えることができます。
この画面で現状を確認してみてはいかがでしょうか?
もしなければ削除されているので、再度AppStoreからインストールしてください。
購入済みの場合は「インストール」のステータスになり、再購入にはならないのでご安心下さい。
詳しくは下のURLを参照してください。
http://support.apple.com/kb/HT1977?viewlocale=ja_JP&locale=ja_JP