What is a physical theory/model?
A given physical theory is typically mathematically modeled by some set $\mathscr O$ of mathematical objects, and some rules that tell us how these objects correspond to a physical system and allow us to predict what will happen to that system.
For example, many systems in classical mechanics can be described by a pair $(\mathcal C, L)$ where $\mathcal C$ is the configuration space of the system (often a manifold), and $L$ is a function of paths on that configuration space. This model is then accompanied by rules like "the elements of $\mathcal C$ correspond to the possible positions of the system" and "given an initial configuration of the system and it's initial velocity, the Euler-Lagrange equations for $L$ determine the configuration and velocity of the system for later times."
What is a symmetry?
If we think of physics as being a collection of such models, we can define a symmetry of a system as a transformation on the set $\mathscr O$ of objects in the model such that the transformed set $\mathscr O'$ of objects yields the same physics. Note, I'm deliberately using the somewhat vague phrase "yields the same physics" here because what that phrase means depends on the context. In short:
A symmetry is transformation of a model that doesn't change the physics it predicts.
For example, for the model $(\mathcal C, L)$ above, one symmetry would be a transformation that maps the Lagrangian $L$ to a new Lagrangian $L'$ on the same configuration space such that the set of solutions to the Euler-Lagrange equations for $L$ equals the set of solutions to the Euler-Lagrange equations for $L'$. Even in this case, it is interesting to note that $L$ need not be invariant under the transformation for this to be the case. In fact, one can show that it is sufficient for $L'$ to differ from $L$ by a total time derivative. This brings up an important point;
A symmetry does not necessarily need to be an invariance of a given mathematical object. There exist symmetries of physical systems that change the mathematical objects that describe the system but that nonetheless leave the physics unchanged.
Another example to emphasize this point is that in classical electrodynamics, one can make describe the model in terms of potentials $\Phi, \mathbf A$ instead of in terms of the fields $\mathbf E$ and $\mathbf B$. In this case, any gauge transformation of the potentials will lead to the same physics because it won't change the fields. So if we were to model the system with potentials, then we see that there exist transformations of the objects in the model that change them but that nonetheless lead to the same physics.
How do groups relate to all of this?
Often times, the transformations of a model that one considers form actions of groups. A group action is a kind of mathematical object that associates a transformation on a given set with each element of the group in such a way that the group structure is preserved.
Take, for example, the system $(\mathcal C, L)$ from above. Suppose that $\mathcal C$ is the configuration space of a particle moving in a central force potential, and $L$ is the appropriate Lagrangian. One can define an action $\phi$ of the group of $G= \mathrm{SO}(3)$ of the set of rotations $R$ one the space of admissible paths $\mathbf x(t)$ in configuration space as follows:
\begin{align}
(\phi(R)\mathbf x)(t) = R\mathbf x(t).
\end{align}
Then one can show that the Lagrangian $L$ of the system is invariant under this group action. Therefore, the new Lagrangian yields the same equations of motion and therefore the same physical predictions.
Often times the objects describing a given model involve a vector space. For example, the state space of a quantum system is a special kind of vector space called a Hilbert space. In such cases, it is often useful to consider a certain kind of group action called a group representation. This leads one to study an enormous and beautiful subject called the representation theory of groups.
Are groups the end of the story?
Definitely not. It is possible for symmetries to be generated by other kinds of mathematical objects. A common example is that of symmetries that are generated by representations of a certain kind of mathematical object called a Lie algebra. In this case, as in the case of groups, one can then study the representation theory of Lie algebras which is, itself, also an huge, rich field of mathematics.
Even this isn't the end of the story. There are all sorts of models that admit symmetries generated by more exotic sorts of objects like in the context of supersymmetry where one considers objects called graded Lie algebras.
Most of the mathematics of this stuff falls, generally, under the name of representation theory.