The key idea is that the spectrum of a $C^*$-algebra means spectrum in the sense of a ring, and the spectrum of a ring is related to eigenvalue decomposition for a special choice of ring. Wikipedia has a relatively good exposition of these topics, so here's what I took away from it.
Suppose $T$ is an operator on a n.v.s. $V$ over $\mathbb{C}$. I'll remind you that $\mathbb{C}[T]$ is the ring of formal power series in $T$ with coefficients in $\mathbb{C}$, and then claim expect there to be some sort of decomposition (in the sense of isometric isomorphism) $$V\cong\bigoplus_{\lambda\in\sigma(T)}{\mathbb{C}[T]/(T-\lambda)^{m(\lambda)}}$$ This is certainly true in the finite-dimensional case — it's called the Chinese Remainder Theorem for f.g. modules over a PID. In the infinite-dimensional case, we can get close with very few assumptions; if $V$ is Hilbert and $T$ normal, then there exists a projection-valued measure $\mu_T$ on $\sigma(T)$ such that $$T=\int_{\sigma(T)}{\lambda\,\mu_T(d\lambda)}$$ where the integral exists in a suitably weak topology. If we interpret each "value" of the absolutely continuous part of $\mu_T$ as a subspace isomorphic to $\mathbb{C}[T]/(T-\lambda)$, then we can see that all we've done is replace the direct sum with a more general method of knitting together n.v.ses. For a reference on this, see [1]; for the non-Hilbert case, see [2] and maybe do a few Google searches.
Now, in each case (both finite-dimensional and infinite), there are no zero-divisors of $\mathbb{C}[T]/(T-\lambda)^{m(\lambda)}$ except nilpotents, so $(T-\lambda)$ is prime. In algebraic geometry, a prime ideal corresponds to an irreducible variety (irreducible vanishing set of a bunch of polynomials). This suggest we interpret the eigenvalues as algebraic varieties; endow them with the Zariski topology and study the spectrum of a operator as a topological space.
We can replace $\mathbb{C}[T]$ with an arbitrary commutative unital $\mathbb{C}$-algebra to obtain the spectrum of a ring — no problem. The key picture now is that we are looking at $\mathbb{C}[T_1,T_2,\dots]$, and the spectrum describes the eigenvalues of all the mutually diagonalizable operators.
In the $C^*$-algebra case, the above almost goes through, but not quite. Because $C^*$-algebras are, in general, not commutative, we need to use a generalization of a prime: an ideal is primary if it annihilates a simple left module. This gives us extra copies of the same ideal, up to isomorphism in the category of $C^*$-algebras (unitary equivalence). So now we have to quotient out by that.
Putting it all together, we have the following definition.
The spectrum of a $C^*$-algebra is quotient of the set of primary ideals with the Zariski topology by unitary equivalence.
And now to a few specific questions.
Why is $S$ involved? There's no point in using more points. As I mentioned above, $S$ is already the "set of mutual eigenvalues for all the operators studied," so your operators will be simultaneously constant on subsets if you add more points.
What is the Gelfand map? Each operator is uniquely determined by its action. So look at all possible ways a $C^*$-algebra could act on a space — its representations. Theoretically, there should be an isomorphism between the algebra and its relations. For the special case most useful towards building intuition, look up Pontryagin duality.