As described in the documentation
http://developer.android.com/reference/android/os/Handler.html
"Each Handler instance is associated with a single thread and that thread's message queue."
When you are about to finish your activity, e.g. in onDestroy()
you also need to cancel the callback for the runnable it was started for:
mHandler.removeCallbacks(previouslyStartedRunnable);
You can do that even without checking if runnable was already fired while your activity was active.
UPDATE:
There are two additional cases to be considered:
1.) You have implemented your Handler in a way that you created new class for the Runnable, e.g.
private class HandleUpdateInd implements Runnable...
Usually you need to do that if you have to start delayed runnable with current set of parameters (which may change until runnable fires). To cancel it you need to use
mHandler.removeCallbacksAndMessages(HandleUpdateInd.class);
2.) If you are using inline call (JPM thanks for the comment)
handler = new Handler() { public void handleMessage(Message msg) { ... } };
Then you need to define "what" value for that Message. Later on, if you need to cancel it you can use
handler.removeMessages(what);
to perform that task.