You need to have at least firmware 2.0 installed. To check the firmware, connect your iPod to iTunes and it will tell you on the Summary screen. Also, you can go into Settings on your iPod, select General and then About, and it will say the same thing.
If your iPod already has the App Store icon on the screen, then you can download and install Apps already.