How do we know what happens to stars during their life cycle? It is common knowledge than Sun-sized stars will eventually become red giants, and later they will get gradually smaller again until they cool down into a brown dwarf, and that bigger stars can explode into a supernova.
However, how can we prove or verify it? Or how was it discovered? We can observe different stars of different sizes and colors, and even some supernova and their remnants were discovered, but as the processes take such a long time, how can we deduce from direct observation how a star changes over time? 
Or was all this done solely by mathematical deduction based on models we built around what we know about nuclear fusion and fission?
 A: 
Or was all this done solely by mathematical deduction based on models we built around what we know about nuclear fusion and fission?

This is pretty much it.  Generally, stars don't evolve fast enough for us to see it happening*, so we're left with a problem more like archaeology: we see stars in various different states, and it's up to us to make a model of how they all fit together. Our "experiments" are numerical.
That said, and despite all the open problems in stellar physics, the model we have is quite simple and works really well in making sense of the various classes of star.  The basic assumptions are basically that stars are self-gravitating spherically-symmetric balls of opaque plasma in hydrostatic and local thermal equilibrium.  This already tells you that the centres are hot and dense enough to initiate nuclear reactions. Adding them into the equations gives the main source of long-term pressure balance.  You also find that in some places, the plasma is unstable to convection, so you have to tack in a model for that too.  From there, it's just a case of letting the models evolve (which is mainly because the reactions change the chemical composition), and you find you can reproduce most major stellar types, and therefore conclude, say, that the Sun will become a red giant.  The quantitative predictions might be a bit off, but qualitatively everything fits together.
There are, however, some stars out there that confuse this picture. The most serious complication, in my opinion, is that stars are often close enough to other stars that they interact, and this can trick you into misunderstanding what's going on. For example, you can read up about the Algol paradox or the blue stragglers, both of which would defy conclusions from the single-star picture. 
Stellar winds are another thing that complicate the picture.  What are we to otherwise make of Wolf-Rayet stars and subdwarf B and subdwarf O stars? They don't come from the simple picture unless we add substantial winds to the model, and our formulae are mostly still empirical.
Plenty of other details remain uncertain, but the simple single-star picture, based on reasonable physical assumptions, explains most of what we see, from which we conclude that it must be at least mostly correct.
*An interesting exception is supernovae.  Not only do we see the supernova evolve, but we're now able to look at images from before the supernova to determine which star was the progenitor.
A: Our ideas about how stars evolve are largely driven by numerical modelling - solving the rather well-understood equations of stellar structure.
There are however multiple, interlocking tests and constraints on these models that tell us we have more-or-less got the right ideas. There are of course "details" left to be sorted out (theories about mixing inside stars, the role of rotation, magnetic fields etc.), but the broad sweep of how stellar evolution occurs is a solved problem. The first test is to see how our models predict the properties of the Sun now. This is important because (a) we can measure these properties very accurately and (b) we can directly estimate the age of the Sun using radioisotope dating of solar system material. Whilst there are some tuneable parameters, we basically find that we can explain the structure, radius, luminosity, neutrino output and helioseismological observations of the Sun using our models, with the mass, composition and age of the Sun as inputs.
Now those models can be used with some confidence to predict the properties of other stars at other ages. The second important constraint on the models then comes from looking at groups of stars with the same age, but with a range of masses. These are found in star clusters, where to first order we can assume that all the stars were born at the same time with the same chemical composition. Our models predict how the luminosity, radius and effective temperatures of such stars should depend on their mass. The models and data can be compared in the Hertzsprung-Russell diagram (luminosity vs temperature), or if we don't know the distance to the cluster, in the surface gravity (which can be determined from spectra) vs temperature diagram. The only free parameter is the age which is then determined by fitting the models to the data.
Clusters can thus be arranged into a sequence according to their ages and we can see how stellar evolution proceeds from one age to the next. We can see that very young clusters contain no red giants and no white dwarfs, indicating that these are later stages of stellar evolution. Clusters that are a little older contain no high mass main-sequence stars (hence they must have short lives) and do contain red giants. i.e. The high mass main sequence stars have evolved to become red giants. Clusters that are a lot older contain no main sequence stars more massive than the Sun, a few red giants and lots of white dwarfs. This tells us that the main sequence lifetime depends inversely on mass, that the red giant phase is relatively short-lived and that most stars end their lives as slowly cooling white dwarfs. And so on...
A third critical test is provided by eclipsing binary stars. In these systems we can measure the mass and radius of both stars and we can also assume that they were born at the same time. The stellar evolution models must be able to match the masses and radii of both components at a single age and using a chemical composition that can be estimated using spectroscopic observations. In many cases we might have binaries with different component masses where the two stars are at different evolutionary stages.
There is no single magic-bullet observation that tells us whether the models are correct. They must explain the ensemble of observations of diverse populations. Only then do we have confidence that our understanding of stellar evolution is basically correct.
