It's common to place the matrix dimensions as subscripts, so you could use
\[
A_{\scriptscriptstyle p\times k}x_{\scriptscriptstyle k\times 1}=b_{\scriptscriptstyle p\times 1}
\]
EDIT: an option would be to show the dimensions only on one slide and to hide them on other slide(s) using something like this:
\[
\onslide<1,2>{A}\only<1>{_{\scriptscriptstyle p\times k}}
\onslide<1,2>{x}\only<1>{_{\scriptscriptstyle k\times 1}} =
\onslide<1,2>{b}\only<1>{_{\scriptscriptstyle p\times 1}}
\]
EDIT2: a variant on Caramdir's solution, but focusing on the contents:
\documentclass{beamer}
\usepackage{tikz}
\usefonttheme[mathonly]{serif}
\begin{document}
\begin{frame}
\begin{center}
\begin{tikzpicture}[every node/.style={inner sep =1pt},dim/.style={red!50!black}]
\onslide<1->{\node (meq) at (0,0) {$Ax=b$};}
\onslide<2->{\node[dim] (A) at (-1,-0.8) {$\scriptscriptstyle p\times k$};
\draw[->,red!50!black] (A) -- (meq.200);}\pause
\onslide<3->{\node[dim] (x) at (-0.25,-0.8) {$\scriptscriptstyle k\times 1$};
\draw[->,red!50!black] (x) -- (meq.215);}\pause
\onslide<4->{\node[dim] (b) at (1,-0.8) {$\scriptscriptstyle p\times 1$};
\draw[->,red!50!black] (b) -- (meq.341);}\pause
\end{tikzpicture}
\end{center}
\end{frame}
\end{document}