For a nonzero prime ideal $\mathfrak p$ in $\mathcal O_K$ lying over $p$ and $m \geq 1$, the quotient ring $\mathcal O_K/\mathfrak p^m$ is unchanged up to isomorphism if we replace $\mathcal O_K$ by its localization at $\mathfrak p$ or by its completion at $\mathfrak p$ (and the modulus also changes to the ideal it generates in the localization or completion). The ramification index $e = e(\mathfrak p|p)$ and residue field degree $f = f(\mathfrak p|p)$ are unchanged by localizing or completing at $\mathfrak p$.

Let $A$ be the completion of $\mathcal O_K$ at $\mathfrak p$, so in $A$ we can write $p = \pi^e u$ for some uniformizer $\pi$ and $u \in A^\times$. Then 
$\mathcal O_K/\mathfrak p^e \cong A/(\pi^e) = A/(p)$. (In this step it's important that the exponent $e$ is the ramification index of $\mathfrak p$ over $p$.) The ring $A$ is the ring of integers of the completion $K_\mathfrak p$. Even though $\mathcal O_K$ need not be monogenic, completions *are* monogenic: the ring of integers of every finite extension of $\mathbf Q_p$ has a power basis over $\mathbf Z_p$, so $A = \mathbf Z_p[\alpha]$ for some $\alpha \in A$. That there is a power basis over $\mathbf Z_p$ is the key fact you were missing. 

Let $\alpha$ have minimal polynomial $F(x)$ in $\mathbf Z_p[x]$, so $F(x)$ is irreducible over $\mathbf Z_p$ and 
$A \cong \mathbf Z_p[x]/(F(x))$ as rings. Viewing both sides as $\mathbf Z_p$-modules and computing their $\mathbf Z_p$-ranks shows $[K_\mathfrak p:\mathbf Q_p] = \deg F$, so 
$$
\deg F = e(\mathfrak p|p)f(\mathfrak p|p) = ef.
$$

Using $F(x)$, 
$$
\mathcal O_K/\mathfrak p^e \cong A/(p) = \mathbf Z_p[\alpha]/(p) \cong \mathbf Z_p[x]/(p,F(x)) \cong \mathbf F_p[x]/(\overline{F}(x)).
$$



The mod $p$ reduction $\overline{F}(x)$ in $\mathbf F_p[x]$ has a factorization into monic irreducibles. All monic irreducible factors of $\overline{F}(x)$ are the same, because if that were not the case then we could write $F(x) \equiv G(x)H(x) \bmod p$ for nonconstant monic $G(x)$ and $H(x)$ where $\gcd(G \bmod p,H \bmod p) = 1$ in $\mathbf F_p[x]$, and then by Hensel's lemma (the one about lifting relatively prime factorizations, not just about lifting a simple root) we'd get a factorization of $F(x)$ in $\mathbf Z_p[x]$ into nonconstant monic factors, which contradicts the irreducibility of $F(x)$ over $\mathbf Z_p$.  So in $\mathbf F_p[x]$ we must have $\overline{F}(x) = Q(x)^d$ for some monic irreducible $Q(x)$ in $\mathbf F_p[x]$ and $d \geq 1$.  That means
$$
\mathcal O_K/\mathfrak p^e \cong A/(p) \cong \mathbf F_p[x]/(Q(x)^d)
$$
as rings.


We will now show 
$$
d = e = e(\mathfrak p|p), \ \ \deg Q = f = f(\mathfrak p|p).
$$
Let $k = \mathcal O_K/\mathfrak p$, which is the residue field of $\mathcal O_K$ at $\mathfrak p$, so $\dim_{\mathbf F_p}(k) = f$ by definition. Residue fields are unchanged up to isomorphism by completion, so $k \cong A/(\pi)$. The local ring $A/(p) = A/(\pi^e)$ has maximal ideal $(\pi)/(\pi^e)$ and residue field $A/(\pi)$, while the local ring $\mathbf F_p[x]/(Q(x)^d)$ has maximal ideal $(Q(x))/(Q(x)^d)$ and residue field $\mathbf F_p[x]/(Q(x))$. Isomorphic local rings have isomorphic residue fields, so $k \cong \mathbf F_p[x]/(Q(x))$. Computing $\mathbf F_p$-dimensions of both sides, 
$$
f = \deg Q.
$$
Returning to $F$, which is monic and reduces mod $p$ to $Q(x)^d$, we can now say 
$$
\deg F = \deg \overline{F} = d\deg Q = d f
$$ 
and we already saw $\deg F = ef$, so 
$$
d = e.
$$
Thus 
$$
\mathcal O_K/\mathfrak p^e \cong A/(p) \cong \mathbf F_p[x]/(Q(x)^e), \ \ \deg Q = f.
$$

The last step is to show $\mathbf F_p[x]/(Q(x)^e) \cong k[t]/(t^e)$ as rings. Since $Q(x)$ is irreducible in $\mathbf F_p[x]$, the ring $\mathbf F_p[x]/(Q(x)^e)$ is unchanged up to isomorphism if we replace $\mathbf F_p[x]$ with its $Q$-adic completion $\mathbf F_p[x]_Q$: 
$$
\mathbf F_p[x]/(Q(x)^e) \cong \mathbf F_p[x]_Q/(Q(x)^e)
$$
as rings. 
The residue field of $\mathbf F_p[x]_Q$ is isomorphic to $\mathbf F_p[x]/(Q(x))$, which is isomorphic to $k$. The completion $\mathbf F_p[x]_Q$ is the ring of integers of the $Q$-adic field completion $\mathbf F_p(x)_Q$, and the structure of local fields of positive characteristic says they are all isomorphic to the formal Laurent series field over the residue field. Thus $\mathbf F_p(x)_Q \cong k((t))$ as valued fields, so their rings of integers are isomorphic: $\mathbf F_p[x]_Q \cong k[[t]]$. The isomorphism identifies powers of the maximal ideal on both sides, 
and the maximal ideal of $\mathbf F_p[x]_Q$ is $(Q)$ since $Q$ is a uniformizer in the $Q$-adic completion. Thus 
$$
\mathbf F_p[x]_Q/(Q^m) \cong k[[t]]/(t^m)
$$
for each $m \geq 1$. Both sides simplify to quotient rings of $\mathbf F_p[x]$ and $k[t]$, just as $\mathbf Z_p/(p^m) \cong \mathbf Z/(p^m)$:
$$
\mathbf F_p[x]/(Q^m) \cong k[t]/(t^m).
$$
Taking $m = e$, we get
$$
\mathbf F_p[x]/(Q^e) \cong k[t]/(t^e),
$$
so $\mathcal O_K/\mathfrak p^e \cong A/(p) \cong \mathbf F_p[x]/(Q^e) \cong k[t]/(t^e)$.