Other is the measure of used space on the iPod not taken up by Audio, Video & Photos. This includes the iPod's library and artwork plus any files you may have copied to your iPod in disk mode. The overhead for the library & artwork data is typically 1-2% of the size of the media, e.g. for 1Gb of Audio & Video expect to have around 15mb of Other. This information is needed for the iPod's operation and cannot be removed.
If you have significantly larger amounts of Other, not related to files you've intentionally placed on the iPod, then these are probably disconnected copies of your media files or iPod libraries left over from failed sync operations. The only way to recover the space is to do a full restore.
If you have copies of all your media in your iTunes library this isn't a problem, but if you've been manually managing the content then you might need to try to recover the files from it first. See this post by Zevoneer on transferring files from the iPod to your computer. Some of the tools rely on the iPod having a healthy library however the manual method mentioned towards the end of the post should work regardless.
Note restoring should clear all files from the iPod's drive however sometimes it doesn't actually seem to work. Options include manually deleting all visible & hidden files & folders via Explorer/Finder or formatting the drive.
When repopulating the drive you may find breaking the process up into smaller stages makes it less likely to fail.
Break up large transfers
In iTunes select the menu item File... New Smart Playlist. Change the first drop-down box to Playlist, the next to is and the next to Music or whatever playlist holds the bulk of the content you want on your device. Tick against Limit to, type in say 10, then change the drop-down to GB, and set the last drop-down to artist. When you click OK you can enter a name for the playlist, e.g. Transfer. Now sync this playlist to your iPod rather than your entire library. When the sync is complete modify the rule (File... Edit playlist) to increase the size by your chosen amount, then sync and repeat. You can experiment with different size increments, if it doesn't work just choose something a bit smaller until it works each time. Before long you should have all your music on your iPod. Once that's done you can move on to other media such as podcasts, videos, photos, playlists etc.