Counting when there are two inclusive conditions. 
How many 8-bit sequences begin with $101$ OR (inclusive) have a $1$ as
  their fourth bit?

For the first condition, we need only to decide the values of the $5$ other bits, so there are
$$2^5$$
sequences starting with $101$.
For the second condition, we have to decide the values of the other $7$ bits, so there are
$$2^7$$
sequences with a $1$ as their fourth bit.

The final answer, however, surely cannot be
$$2^5+2^7$$
Because $2^5$ includes some scenarios with a $1$ as the fourth digit, whereas $2^7$ includes cases with a $101$ at the beginning, so I would be over-counting this. What do I do in this case?

The big problem here: if $A_1$ is the set of sequences which satisfy the first property and $A_2$ is the set of sequences which satisfy the second, then (exactly as you suggest), $\lvert A_1\rvert+\lvert A_2\rvert$ over-counts.
However, it over-counts in a very predictable way: namely, any sequence which is in exactly one of the sets is counted only once, while any sequence in $A_1\cap A_2$ is counted twice!  So, this tells us that
$$
\lvert A_1\rvert+\lvert A_2\rvert=\lvert A_1\cup A_2\rvert+\lvert A_1\cap A_2\rvert.
$$
But, we can rearrange this to get
$$
\lvert A_1\cup A_2\rvert=\lvert A_1\rvert+\lvert A_2\rvert-\lvert A_1\cap A_2\rvert.
$$
So, you need only compute $\lvert A_1\cap A_2\rvert$ -- that is, the number of sequences which satisfy BOTH properties -- and subtract it from your previous total.
(This is actually the most basic form of a more general process called the inclusion-exclusion principle.)
