I basically agree with what Code Monkey just said. I have a 3.5
terabyte library, so I long ago gave up on the idea of carrying my entire media collection around with me
With the iOS devices, 16-32GB is kind of the "sweet spot" depending on your app usage. I found 16GB to be more than tolerable for media content, including video, but some of the apps can push that requirement up a bit -- the better games tend to run 100-200MB each, and the turn-by-turn GPS navigation apps are especially huge at around 1.5-2GB. That said, you likely won't have any use for GPS apps on an iPod touch unless you plan to buy a car dock with an external GPS receiver and use it as a GPS in your car.
The HD video recording is definitely something else to consider. You can't record in SD on the iPod touch -- it's 720p HD or nothing, and you can expect that to take up around 80MB per minute of video recording, which means a half-hour of video will eat up around 2.5GB of storage. This is something to keep in mind if you plan to shoot and store a lot of video. Even a dozen smaller clips can quickly add up.
Similarly, due to the higher-resolution Retina Display, photos synced to the iPod touch from iTunes will be larger than they would have been on previous models, as iTunes resizes photos when syncing for the screen resolution of the target device.
That said, I'm perfectly comfortable with my 32GB iPhone 4, even with a GPS navigation app installed and several hundred photos synced onto it. I don't keep very many movies or TV shows on my device, however, as I would never watch a full-length movie on my device except when I'm stuck on a plane or a train for a few hours with nothing better to do.