This is just an arbitrary testimony of an often repeated slogan:
"The group of automorphisms of a given structure is often a powerful tool for studying this structure." D. Lascar, On the Category of Models of a Complete Theory
I wonder why this should be so when thinking of the fact that (for example) almost all graphs have a trivial automorphism group. And only very few - if any - graphs have an automorphism group that allows literally to tell the graph from it.
How then is this slogan to be understood? For which kinds of structures does it make sense, resp. in which sense?
Side question: Is it true, that when the automorphism group of a graph is isomorphic to the full symmetric group $S_n$, then the graph has to be the complete graph $K_n$ or its complement?
Lascar says often, not always. The philosophy -- which you correctly link back to Klein's Erlangen Program; I think you would do well to study that and read what Klein has to say about it -- certainly works better for structures which have large, rich automorphism groups. Klein's original motivation was the observation that many of features of a geometry are determined by its group of isometries, which is usually a Lie group of positive dimension. Geometries with nonisomorphic isometry groups are profoundly different. Geometries with isomorphic isometry groups often have some deep commonalities.
I think it is too broad a question to ask for anything like a comprehensive description of the structures for which the automorphism group plays a key role. Here are two important examples:
The classification of fiber bundles on a (sufficiently nice) topological space depends only on the automorphism group of the fiber, not on the homeomorphism type of the fiber. This leads to a description/construction of fiber bundles on a space in terms of $1$-cocycles with coefficients in the automorphism group. Also the notion of "reduction of the structure group" is a key one in the study of fiber bundles. E.g. a paracompact differentiable manifold is orientable if the structure group of the tangent bundle can be reduced to $\operatorname{GL}_n(\mathbb{R})^+$. It admits a Riemannian metric iff the structure group can be reduced to $O_n(\mathbb{R})$. In fact the latter is always the case, and that can be understood (among other ways) by understanding the way that $O_n(\mathbb{R})$ sits inside $\operatorname{GL}_n(\mathbb{R})$.
A closely related principle is the principle of Galois descent: if $V_{/K}$ is an algebraic structure defined over a field (examples: a $K$-algebra, a variety, a group variety), then the set of twisted forms of $V_{/K}$ -- namely those objects $W_{/K}$ which become isomorphic to $V$ over the algebraic closure of $K$ -- are again parameterized by $1$-cocycles with coefficients in the automorphism group of $V$. In particular, when two objects which have isomorphic automorphism groups, there is a bijection between the twisted forms. Here the case of a trivial automorphism group is not a trivial case: when the automorphism group is trivial, there are no twisted forms other than $V$.
One could go on forever in the above manner, so I'll limit myself now to graph theory.
This follows easily from the fact that you mentioned: for all sufficiently large $n$, there is a connected graph $R_n$ on $n$ vertices with trivial automorphism group (and indeed the proportion of such graphs among all connected graphs approaches $1$ as $n$ approaches infinity). Then given a graph $G$ with $n$ vertices, $G \coprod R_{n+1}$ must have the same automorphism group as $G$.
We may assume $n \geq 2$, and then $S_n$ acts doubly transitively on $\{1,\ldots,n\}$, in other words, given any two pairs of distinct vertices, there is a graph automorphism taking one to another. Since the graph is nonempty, there are two vertices $v_1$ and $v_2$ connected by an edge. It follows that every pair of vertices is connected by an edge.
By the way, the fact that most finite graphs have trivial automorphism group only means that one cannot use the automorphism group as a tool to classify finite graphs (which is a rather hopeless problem anyway). It certainly does not mean that the automorphism group of a graph is not a highly interesting and useful invariant. In practice, the individual graphs of most interest tend to be those with a large, interesting automorphism group (and recall that by a theorem of Frucht, every group occurs up to isomorphism as an automorphism group of some graph). For instance Cayley graphs of groups are extremely important, and there the automorphism group acts simply transitively. Conversely, a celebrated theorem of G. Sabidussi says that any graph which admits a simply transitive subgroup $G$ of automorphisms must be a Cayley graph on the group $G$. So the automorphism group of a graph can tell us important information about the graph, especially when regarded as a permutation group on the set of vertices rather than as an abstract group.