Q: missing app store icon

If it was Restored using iTunes, the current OS on it may be iPhone OS 2.x, or even 1.x.  I think 2.x should have the App Store on it, but 1.x would not (because the App Store did not exist until year two).  You can check the OS version by going to Settings, then General, then About.  What does it say for Version?  You can also get this info on the iTunes window (on the computer), on the iPod's Summary screen.

Like the 1st gen iPhone, which I have and use, it can run up to iPhone OS 3.1.3.  However, on an iPod touch, the yearly software upgrade required paying a small fee (until iOS 4).  This document explains how to purchase the upgrade to "iOS 3.1."

http://support.apple.com/kb/HT2052

It costs $4.95, from the iTunes Store.

Once you have iPhone OS ("iOS") 3.1.3 installed, you should have an icon for the App Store. 

Unfortunately, a large percentage of apps require a later version of iOS (and/or more recent hardware).  It is actually much easier to search the App Store from iTunes, because you are using the large screen and faster speed of your computer.  Run iTunes, open the iTunes Store, and click on App Store on the "bar."  The app description states iOS and hardware requirements.  You want older apps, so a good way to search is to get a list of apps in a specific category, list it by app release date, and go toward the bottom of the list.

You can download apps on your computer in iTunes and then sync them to your iPod touch.