A couple ways to do it...
In the iPod's settings, there's a checkbox where you can basically tell it to fill the iPod with random songs from your library whenever you sync.
As far as narrowing down the randomness, the first thing that comes to mind is smart playlists. You can create a smart playlist, and rather than adding songs to it yourself, you define conditions for the playlist, eg. all songs that have the 'rock' genre, or all songs from the last decade.
In fact, iTunes already creates a few of these playlists for you. You'll probably notice playlists called 'Recently Added', 'Most Played' and '90's Music'. These are some of the default smart playlists iTunes gives you, just examples of ways to organize your iTunes library.