Let me try to explain the CM connection, as I think it really is the most intuitive way to understand this. Fear not, this is not a one line answer!

I'll be working with $\mathbb{C}$ throughout. Every elliptic curve over $\mathbb{C}$ is of the form $\mathbb{C}/\Lambda$, where $\Lambda$ is a discrete rank two sublattice of $\mathbb{C}$. This description is not unique: If $\alpha$ is any nonzero complex number, then $\mathbb{C}/\Lambda$ and $\mathbb{C}/\alpha \Lambda$ define the same elliptic curve.
If we have a two elliptic curves, $\mathbb{C}/\Lambda_1$ and $\mathbb{C}/\Lambda_2$, and a map $\phi$ between them, then there is a unique complex number $\beta$ such that $\beta \Lambda_1 \subseteq \Lambda_2$ and $\phi$ arises as the map which takes the coset $z+\Lambda_1$ to the coset $\beta z + \Lambda_2$.

I'll first explain the basic idea of complex multiplication, and then talk about the Atkin-Lehner case. Complex multiplication is all about describing the possible self maps of an elliptic curve. Consider a complex number $\beta$ and a lattice $\Lambda$. When does multiplication by $\beta$, as a map from $\mathbb{C}$ to $\mathbb{C}$, descend to a map from $\mathbb{C}/\Lambda$ to $\mathbb{C}/\Lambda$? This happens, if and only if $\beta \Lambda \subseteq \Lambda$.

Now, let's fix $\beta$ and consider which $\Lambda$ have this property. Notice that, if $\lambda$ is a nonzero element of $\Lambda$, and $\theta$ is any element in the ring $\mathbb{Z}[\beta]$, then $\theta \lambda$ is in $\lambda$. This means that $\mathbb{Z}[\beta] \cdot \lambda$ must form a discrete sublattice of $\Lambda$, so the ring $\mathbb{Z}[\beta]$ must be a discrete sublattice of $\mathbb{C}$.

**Case 1:** $\mathbb{Z}[\beta]$ is a rank $1$ sublattice of $\mathbb{C}$. In this case, $\beta$ is in $\mathbb{Z}$ and $\beta \Lambda \subseteq \Lambda$ for every $\Lambda$.

**Case 2:** $\mathbb{Z}[\beta]$ is a rank $2$ sublattice of $\mathbb{C}$. In this case (this is not obvious) $\mathbb{Z}[\beta]$ must either be of the form $\mathbb{Z}[\sqrt{-d}]$ or $\mathbb{Z}[(1+\sqrt{-d})/2]$, where $d>0$ and, in the latter case, $d$ must be $3 \mod 4$. In this case, there are finitely many lattices $\Lambda$ such that $\beta \Lambda \subseteq \Lambda$ (up to treating $\Lambda$ and $\alpha \Lambda$ as equivalent, as mentioned in the second paragraph.). The number of these lattices is more or less the class number of $\mathbb{Q}[\sqrt{-d}]$. (It is exactly this if $d$ is square free and $1$ or $2$ mod $4$; otherwise there are some details to fix up.)

**Case 3:** $\mathbb{Z}[\beta]$ is not a discrete sublattice of $\mathbb{C}$. As discussed above, in this case there are no $\Lambda$'s for which $\beta \Lambda \subseteq \Lambda$.

Now, for the Atkin-Lehner connection. The modular curve $Y_0(p)$ (the one without the cusps) parameterizes ordered pairs $(\Lambda_1, \Lambda_2)$, where $\Lambda_2$ is an index $p$ sublattice of $\Lambda_1$, and where $(\Lambda_1, \Lambda_2)$ is identified with $(\alpha \Lambda_1, \alpha \Lambda_2)$ for any nonzero complex number $\alpha$.

The Atkin-Lehner involution sends $(\Lambda_1, \Lambda_2)$ to $(\Lambda_2, p \Lambda_1)$. So a fixed point of Atkin-Lehner must correspond to a pair $(\Lambda_1, \Lambda_2)$ such that $(\Lambda_2, p \Lambda_1) = (\alpha \Lambda_1, \alpha \Lambda_2)$ for some $\alpha$. In particular,
$$p \Lambda_1 = \alpha (\alpha \Lambda_1) = \alpha^2 \Lambda_1.$$

Set $\gamma = \alpha^2/p$. Then both $\gamma$ and $\gamma^{-1}$ take $\Lambda_1$ to itself, so both $\mathbb{Z}[\gamma]$ and $\mathbb{Z}[\gamma^{-1}]$ are discrete lattices. Looking at the case by case analysis above, one works out that $\gamma$ is one of $1$, $-1$, $\pm i$, $\pm e^{2 \pi i/6}$ and $\pm e^{4 \pi i/6}$. Now, $\alpha = \sqrt{p \gamma}$ and we have $\alpha \Lambda_1 = \Lambda_2 \subset \Lambda_1$. So $\sqrt{p \gamma}$ must also generate a discrete sublattice of $\mathbb{C}$. Looking at the previous list of cases, the only one that survives is $\gamma = -1$ and $\alpha = \sqrt{-p}$.

So the fixed points of Atkin-Lehner come from lattices $\Lambda_1$ such that $\sqrt{-p} \Lambda_1 \subset \Lambda_1$; for each such lattice $\Lambda_1$ we get the fixed point $(\Lambda_1, \sqrt{-p} \Lambda_1)$. Using the previous discussion, the number of such $\Lambda_1$'s is essentially the class number of $\mathbb{Q}(\sqrt{-p})$.