I never found an elegant solution for getting last.fm submissions from the iPod, but jscrob2 seems perfect. It’s a plugin for iTunes that submits anything you listen to in iTunes but also submits anything you played on the iPod when you sync it up.
Click here for the jscrob2 website
Update [14th June] – the above link is dead, but I found another site with the plugin download