Cardinality of a power set is given be $2^n$. Why? Cardinality of power set of $A$ is determined by $2^n$, where n is the number of elements in Set $A$. How does this formula work?
I was taught that there are $n$ elements in Set $A$ and each element has a choice of either being in the power set or not i.e., $2$ choices. Hence $\underbrace{ 2\times 2\times 2\times 2 \cdots}_{n\; times}  $. 
But I don't understand why the element's choice of either being in the power set or not helps us in determining the cardinality of the power set.
 A: 
I was taught that there are n elements in Set A and each element has a choice of either being in the power set or not i.e., 2 choices.

By definition, the power set of $A$ is the set of all subsets of $A$. The power set of $A$ does not contain elements of $A$, it contains subsets of $A$.
In how many ways can you choose a subset (say, $X$) of $A$? Well, every element in $A$ has a choice of either being in $X$ or not, i.e. $2$ choices. Thus there are $2^n$ ways you can form a subset $X$. Thus the total number of subsets is $2^n$.
To summarize: your mistake seems to be that you have swapped "choice being in $X$" (where $X$ is a subset) to "choice being in the power set". 
A: This is a nice exercise for mathematical induction. It follows from these observations:
Assume that $X$ is a nonempty set and let $x_0\in X$ be a fixed element. Now let
$$T_{x_0}=\{A\subset X\ |\ x_0\in A\}$$
$$U_{x_0}=\{B\subset X\ |\ x_0\not\in B\}$$
The following properties are straightforward:
$$U_{x_0}=P(X\backslash\{x_0\})$$
$$P(X)=T_{x_0}\cup U_{x_0}$$
$$T_{x_0}\cap U_{x_0}=\emptyset$$
The crucial observation is that
$$|T_{x_0}|=|U_{x_0}|$$
I encourage you to construct such a bijection by yourself. All those facts together give
$$|P(X)|=2\cdot |P(X\backslash\{x_0\})|$$
and now you apply mathematical induction. Can you complete the proof?
A: Impose an order on $A$. You can think of each subset in terms of the $n$-bit string that tells you which elements it has, with the $i$th bit $1$ if the $i$th element of $A$ is to be included, or $0$ if it isn't. If $A$ is infinite so that $A$ is a transfinite cardinal, this argument still works (but then your string is infinite, and if uncountable you shouldn't even think of it as a string, but rather a function from elements of $A$ to $\{0,\,1\}$ - which also means we don't need to order $A$ any more), so @freakish's use of induction, which wouldn't carry over to that case, isn't needed. However, this is really how we define $2^n$ for $n$ transfinite.
A: Computer scientists favorite proof...
Let $A = \{a_1, \ldots, a_n\}$ be a set. A subset of $B$ can be represented by a bit vector $b \in \{0,1\}^n$ where 
$$
b_i = \begin{cases}
1 &\text{if $a_i \in B$}\\
0 &\text{if $a_i \notin B$}
\end{cases}
$$
For instance, the subset $\{2,3, 5, 7\}$ of $\{1, 2, \ldots, 10\}$ is represented by the bit vector $(0,1,1,0,1,0,1,0,0,0)$. This gives you a bijection between $\mathcal{P}(A)$ and $\{0,1\}^n$ and thus $|\mathcal{P}(A)| = 2^n$.
