Let $p$ be a prime. For any positive integer $n$ let $\Bbb{F}_{p^n}$ be the finite field with $p^n$ elements. Let V be a vector space over $\Bbb{F}_{p^n}$-vector space of dimension $d$. Prove that the dimension of V as an $\Bbb{F}_p$-vector space is $nd$.
Let $\beta={v_1,,...,v_d}$ be a basis for V as a $\Bbb{F}_{p^n}$-vector space. Let $\gamma={1,a,a^2,...,a^{n-1}}$ be a basis for $\Bbb{F}_{p^n}$ as a $\Bbb{F}_p$-vector space. How am I supposed to construct a basis for $V$ as a $\Bbb{F}_{p^n}$- vector space?
As someone else said, this is indeed a common argument. As you noticed, $\mathbb{F}_{p^n}$ is a $\mathbb{F}_p$-vector whose dimension is $n$.
We could argue with more generality and prove the following fact:
You may prove it using the following general argument: Suppose $\left \{v_1,\cdots ,v_d\right \}$ is a basis for $V$ as $E$-vector space. Suppose $\left \{e_1,\cdots ,e_n\right \}$ is a basis for $E$ as a $k$-vector space.
I claim that $B=\left \{e_jv_i:i=1,\cdots ,d;j=1,\cdots ,n\right \}$ is a basis for $V$ as a $k$-vector space.
We have to show that $B$ generates $V$ as a $k$-vector space, and that its elements are $k$-linearly independent.
Consider the first assertion: take any $v\in V$ and write it down as $v=\sum_{i=1}^da_iv_i$, where $a_i\in E$. Since $\left \{e_1,\cdots ,e_n\right \}$ is a basis for $E$ as a $k$-vector space, for every $i$ you can write $a_i=\sum_{j=1}^n\lambda_{ij}e_j$, where $\lambda_{ij}\in k$. Now return to the expression of $v$ to find $v=\sum_{i=1}^d\left (\sum_{j=1}^n\lambda_{ij}e_j\right )v_i=\sum_{i=1}^d\sum_{j=1}^n\lambda_{ij}e_jv_i$. This clearly proves that $V$ is generated by $B$ as a $k$-vector space.
Now we should try to prove that the elements of $B$ are $k$-linearly independent. Suppose that $\sum_{i=1}^d\sum_{j=1}^n\lambda_{ij}e_jv_i=0$, where $\lambda_{ij}\in k$. Rewrite this as $\sum_{i=1}^d\left (\sum_{j=1}^n\lambda_{ij}e_j\right )v_i=0$. Since $\sum_{j=1}^n\lambda_{ij}e_j\in E$ for every $i$ and $\left \{v_1,\cdots ,v_d\right \}$ is a basis for $V$ as $E$-vector space, then we find that $\sum_{j=1}^n\lambda_{ij}e_j=0$ for every $i$. But since $\left \{e_1,\cdots ,e_n\right \}$ is a basis for $E$ as a $k$-vector space, we also find that $\lambda_{ij}=0$ for every $i$ and every $j$, which shows that the elements of $B$ are $k$-linearly independent.
Then $B$ is a basis for $V$ as a $k$-vector space, and it obviously has exactly $nd$ elements. $\blacksquare$
If you read carefully the proof (which is very standard, really), you will find the answer to your second question: How to construct a basis for $V$ as a $\mathbb{F}_p$-vector space? Well, you may define $\left \{a^{j-1}v_i:i=1,\cdots ,d;j=1,\cdots ,n\right \}$. The above argument shows that this will work fine.