What exactly is a potential energy surface?
The PES $V({R})$ (where $R$ are the nuclear coordinates, electronic coordinates are usually denoted by $r$) is the electronic energy of any electronic state. So there is one PES for the ground state and many more all the excited states.


  Clearly, $E(\{ R_{\text{nucleus}}\})$ gives a PES, and this PES is the relation:
  $$\{ R_{\text{nucleus}} \} \rightarrow E_{\text{ground state electronic energy}}$$
  However, when I learned about molecular dynamics (also in [wikipedia][1]), a PES is defined to be the relation 
  $$\{ R_{\text{nucleus}} \} \rightarrow E_{\text{energy of the system}}$$


"Energy of the system" is here referring to the "electronic system", so those two relations are the same.


  How do we find this map in practice? 



Your first step is correct, we need to solve for the eigenvalues of the electronic Hamiltonian, for many different parameters $R$. Each electronic eigenvalue is one point on the PES. So in the end we get a discretized representation of the (actually continuous) PES $V(R)$.
The second step is to solve the nuclear Hamiltonian
\begin{equation}
  \hat H_{\mathrm{nuc}} = \hat T_{\mathrm{nuc}} + V(R)
\end{equation}
There is only one such nuclear Hamiltonian for each PES.


So we need to do many times step 1, but only once step 2 (for each electronic state of interest).

How to solve the nuclear Hamiltonian?

This depends on what $V(R)$ looks like. In the simple case of a diatomic molecule, where $R$ becomes just the 1-dimensional internuclear distance, we may approximate it with a Morse potential or harmonic potential. We can fit the parameters of such analytic expressions to our discretized points from step 1 and then use the existing general solutions for those quantum systems. This will give us the vibrational eigenvalues and eigenfunctions.

Another option is to solve the nuclear Hamiltonian on a numeric grid over $R$. The grid is either defined by the points chosen in step 1, or we can interpolate to a new grid. How to solve this is a topic on its own, so will just give one literature reference here: The book "Introduction to Quantum Mechanics - A time-dependent Perspective" by David Tannor covers many things related to your questions (although it can be challenging to read it).