How do we know that some radioactive materials have a half life of millions or even billions of years? If a radioactive material takes a very long time to decay, how is its half life measured or calculated? Do we have to actually observe the radioactive material for a very long time to extrapolate its half life?
 A: Lubos has already answered your question comprehensively. I would like to add just one thing. It is one of the funny things of the theory of probability that you need not have to wait for that long to confirm the half life. For example it has been estimated that proton has a half life of approximately $10^{32}$ years in some grand unified theories. Now in order to observe proton decay one does not have to wait for $10^{32}$ years. You just take some material which has $10^{32}$ numbers of protons. According to the theory of probability you should observe at least one proton decay per year (if a proton doest indeed take $10^{32}$ years to decay). For an easier example, suppose you throw a dice 6 times. The probability of a particular outcome is same or equivalent to throwing 6 dices at once.
A: No, one doesn't need to measure the material for years - or even millions or billions of years. It's enough to watch it for a few minutes (for time $t$) and count the number of atoms $\Delta N$ (convention: a positive number) that have decayed. The lifetime $T$ is calculated from
$$ \exp(-t/T) = \frac{N - \Delta N}{N}$$
where $N$ is the total number of atoms in the sample. This $N$ can be calculated as 
$$N={\rm mass}_{\rm total} / {\rm mass}_{\rm atom}.$$
If we know that the lifetime is much longer than the time of the measurement, it's legitimate to Taylor-expand the exponential above and only keep the first uncancelled term:
$$ \frac{t}{T} = \frac{\Delta N}{N}.$$
The decay of the material proceeds atom-by-atom and the chances for individual atoms to decay are independent and equal. 
To get some idea about the number of decays, consider 1 kilogram of uranium 238. Its atomic mass is $3.95\times 10^{-25}$ kilograms and its lifetime is $T=6.45$ billion years. By inverting the atomic mass, one sees that there are $2.53\times 10^{24}$ atoms in one kilogram. So if you take one kilogram of uranium 238, it will take $2.53\times 10^{24}$ times shorter a time for an average decay, e.g. the typical separation between two decays is
$$t_{\rm average} = \frac{6.45\times 10^9\times 365.2422\times 86400}{2.53\times 10^{24}}{\rm seconds} = 8.05\times 10^{-8} {\rm seconds}. $$
So one gets about 12.4 million decays during one second. (Thanks for the factor of 1000 fix.) These decays may be observed on an individual basis. Just to be sure, $T$ was always a lifetime in the text above. The half-life is simply $\ln(2) T$, about 69 percent of the lifetime, because of some simple maths (switching from the base $e$ to the base $2$ and vice versa).
If we observe $\Delta N$ decays, the typical relative statistical error of the number of decays is proportional to $1/(\Delta N)^{1/2}$. So if you want the accuracy "1 part in 1 thousand", you need to observe at least 1 million decays, and so on.
