Is natural selection actually random?
You are right in a sense. The processes which generate mutations in an organism are stochastic (not quite exactly random, but in most organisms they are effectively random for all intents and purposes). In terms of population genetics, it is considered that mutations occur randomly across the genome and have an equal probability of occurring at a given base pair.
The environment is also random/stochastic in the sense that it occurs mostly independent of mutations which have occurred. Whether or not it is cold one year is independent of the mutations which have occurred within an organism. (Actually that's not quite correct since organisms can generate their own environmental niches and evolve according to them, but I think that is beyond the scope of this question).
What is not random is how the frequency of genetic variants respond to different environments. This is natural selection. Over the long run, we expect genetic variants which increase the fitness of an organism within a given environment will increase in frequency and vice versa. There is a large body of theory and evidence which predicts how a particular variant may change in frequency in response selection of a particular pressure.
As @jamesfq correctly points out, a nice example of selection being non-random on the macro-scale is convergent evolution. For example, aquatic animals such as fish, certain mammals (e.g. Dolphins) and Amphibians and Dinosaurs have independently evolved streamlined bodyplans in order to conserve energy when moving through the water.