It's not easy to visualize [itex]\vec{A}[/itex] or give it a physical meaning since it is a gauge-dependent quantity. What's physical is the magnetic field, [itex]\vec{B}[/itex] which is given by
[tex]\vec{B}=\vec{\nabla} \times \vec{A}.[/tex]
For a constant field, it's easy to get the vector potential. So let's consider
[tex]\vec{B}=B_0 \vec{e}_z.[/tex]
You have quite some freedom to choose the vector potential. You can take always one constraint since it is only defined from [itex]\vec{B}[/itex] up to the gradient of a scalar field. Here, I'd choose the spatial axial gauge
[tex]A_z=0.[/tex]
Then you have
[tex]\vec{B}=\begin{pmatrix}<br />
0 \\ 0 \\ B_0<br />
\end{pmatrix} = \vec{\nabla} \times \vec{A}=\begin{pmatrix}<br />
-\partial_z A_y \\ \partial_z A_x \\ \partial_x A_y-\partial_y A_x<br />
\end{pmatrix}.[/tex]
Obviously our constraint doesn't fix the solutions completely, and you have some more freedom. You can, e.g., set [itex]A_x=0[/itex] and [itex]A_y=B_0 x[/itex]. Then you have
[tex]\vec{A} = B_0 x \vec{e}_y.[/tex]
Around a bar magnet you have to solve the magnetostatic Maxwell equations for a given magnetization of your bar. You find some calculations about this in Sommerfeld's Lectures on Theoretical Physics, vol. III.