Do you have a 1G or 2G iPod? I ask because a 1G can only go to iOS 3.1.3 while a 2G can go to 4.2.1. A 1 G does not have volume buttons on the upper left edge and few apps are available for the 1G now.
If you have a 2G update:
To update
The Settings>General>Software Update comes with iOS 5 and later.
Connect the iPod to your computer and update via iTunes as far as your iPod model allows
iOS: How to update your iPhone, iPad, or iPod touch
A 1G iPod can go to iOS 2.2 via iTunes and iOS 3.1.3 via
Purchasing iOS 3.1 Software Update for iPod touch (1st generation)
https://buy.itunes.apple.com/WebObjects/MZFinance.woa/wa/touchLegacyLandingPage
- A 2G to 4.2.1. Requires iTunes version 10 or higher. If a Mac it requires OSX 10.5.8 or later.
Identifying iPod models
To more easily find compatible apps:
iOSSearch - search the iTunes store for compatible apps.
Apple Club - filter apps by iOS version.
Starting when iOS 7 was released, Apple now allows downloading the last compatible version of some apps (iOS 4.2.1 and later only)
Install the latest compatible version of an app on an earlier version of iOS or OS X
Note the neither the 1G or 2G iPod have the Apple Messages app
