How would Find my iPod work on a locked iPod Touch? In order for an iPod Touch (which has Find My iPod enabled) to let Apple's servers know where it is located (e.g. via Wi-Fi positioning), I believe it needs to transmit the location over Wi-Fi.

Let's assume that the iPod is locked and someone stole it. From what I understand, the iPod will never connect to an unknown Wi-Fi network. This means, that since the person that stole the iPod cannot unlock it and initiate a connection to a Wi-Fi network, the iPod will never connect to a Wi-Fi network, and therefore will never transmit its location back to the original iPod owner.

Note: I realize that the iPod can connect to known networks automatically (i.e. those it has previously connected to), but for the purposes of this question, assume that the only Wi-Fi the iPod has connected to was at the original owner's home. And so, the person that stole it will never bring it back in range of this Wi-Fi hotspot, and thus the iPod will never connect to a Wi-Fi hotspot.

Note that this is less of an issue on an iPhone (or iPad with 3G) since the iPhone has a 3G connection which it could use to transmit its location.

Are my assumptions correct which lead to the conclusion that Find My iPod/iPhone/iPad is basically useless on any non-3G device? Am I missing something? Is there any way to increase the chances of locating your iPod touch in case it does get stolen? (Preferably one which doesn't involve connecting to a bunch of random networks (i.e. in order to have them be "known" networks) in hopes that one day the thief will travel by one with the same name and have it auto-connect to that.)
I'm afraid you're completely right. Apple does even make a statement on its website about it: 



However, there are some alternatives.
But since there is no way to come up with a work around on this problem, 3rd party software, like Undercover allows you to store the latest locations of an iDevice. Where Find my iPod touch will only show you the current location (it doesn't show a history of locations I think), Undercover will save its latest location, as they say on their FAQ page:


  What happens if Undercover is launched when a phone is not connected
  to the net? Will it still transmit its location?
  
  If Undercover is launched on an offline device (no 3G or Wi-Fi), its
  location is saved. As soon as the device goes online and Undercover is
  launched again, saved locations will be transmitted.