My understanding of token based authentication is that upon authentication (perhaps over ssl), a token is passed to the user for cheap user verification on the fly. One implementation of this would be to generate a cookie that is passed to the user for session management.
But, my understanding is that token based auth (at least through cookies) is susceptible to man in the middle attacks like firesheep.
Are there other methods of implementation that skirt this major security issue, or do I have a fundamental misunderstanding of tba?
Your understanding is good. Fundamentally, in terms of how the application sees it, a token may as well be a username and password. If someone has the token, they can authenticate themselves to your application. The main purpose in the case of a http cookie is to avoid leaking the username and password should someone obtain the cookie by means of a cross-site scripting vulnerability (XSS) or otherwise. Yes, given the right circumstances they can "replay" this token to the application as a "man in the middle" but they shouldn't be able to figure out the username/password pairing from it but again this is not guaranteed if the token generating algorithm is weak, say, like if you decided to BASE64 encode the username and password concatenated together and use that as the value.
Typically you keep the token -> user mapping secure on the server side. So ultimately your security is all based around keeping the token safe and ensuring that its lifetime is controlled (e.g. it expires and/or is only valid when given to you from the same IP as that used by the original provider of the credentials - again, just an example)
Hope this helps,
-Oisin