Short answer: they all run on the same thread. If instantiated from an Activity lifecycle callback, they all run on the main UI thread.
Long answer:
A thread may have a Looper, which contains a MessageQueue. In order to use this facility, you would have to create a Looper on the current thread by calling (the static) Looper.prepare(), and then start the loop by calling (the also static) Looper.loop(). These are static because there is only supposed to be one Looper per thread.
The call to loop() usually does not return for some time, but keeps taking messages (“tasks”, “commands” or whatever you like to call them) out of the MessageQueue and handles them individually (e.g. by calling back a Runnable contained in the message). When there are no messages left in the queue, the thread blocks until there are new messages. To stop a Looper, you have to call quit() on it (which probably does not stop the loop immediately, but rather sets a private flag that is checked periodically from the loop, signaling the it to stop).
However, you cannot add messages to the queue directly. Instead, you register a MessageQueue.IdleHandler to wait for a queueIdle() callback, in which you can decide if you wish to to something or not. All handlers are called in turn. (So the “queue” isn’t really a queue, but instead a collection of callbacks to be called regularly.)
Note regarding the previous paragraph: This I actually guessed. I couldn’t find any documentation on that, but it would make sense.
update: see ahcox‘ comment and his answer.
Because this is a lot of work, the framework provides the Handler class to simplify things. When you create a Handler instance, it is (by default) bound to the Looper already attached to the current thread. (The Handler knows what Looper to attach to because we called prepare() earlier, which probably stored a reference to the Looper in a ThreadLocal.)
With a Handler, you can just call post() to “put a message into the thread’s message queue” (so to speak). The Handler will take care of all the IdleHandler callback stuff and make sure your posted Runnable is executed. (It might also check if the time is right already, if you posted with a delay.)
Just to be clear: the only way to actually make a looping thread do something is to post a message to it’s loop. This is valid until you call quit() on the looper.
Regarding the android UI thread: At some point (probably before any activities and the like are created) the framework has set up a Looper (containing a MessageQueue) and started it. From this point on, everything that happens on the UI thread is through that loop. This includes activity lifecycle management and so on. All callbacks you override (onCreate(), onDestroy()…) are at least indirecty dispatched from that loop. You can see that for example in the stack trace of an exception. (You can try it, just write int a = 1 / 0; somewhere in onCreate()…)
I hope this makes sense. Sorry for being unclear previously.